http://www.ieeta.pt/~tos/goldbach.html is worth seeing.

They are investigating the Goldbach conjecture there.

They say:

Let n be an even number larger than two, and let n=p+q, with p and q prime numbers, p<=q, be a Goldbach partition of n. In order to verify the Goldbach conjecture for a given n, it is sufficient to find one of its Goldbach partitions. Our strategy will be to find the minimal Goldbach partition, i.e., the one that uses the smallest possible prime number p.

They also say:

So far, we have tested all consecutive even numbers up to 2·10^17, and double-checked our results up to 10^17. Some extra intervals were also tested. About 157.3 CPU years were used to do all this. At least 28.2% of the work necessary to reach 10^18 is already done.

So, we may assume when solving this problem that the Goldbach conjecture is true. (It is because upper limit is only 10^9 which is much less than 10^17 :-).

> But how to solve it fast?

> I don't know.

>

Neither do I.

But I tried looking through all even numbers 2..100 000 000 and finding minimal Goldbach partitions for them. The maximal p that I had used was 1093.

More details:

2..100 000 000 -> maxP was 1093

2..10 000 000 -> maxP was 751

2..1 000 000 -> maxP was 523

2..100 000 -> maxP was 293

2..10 000 -> maxP was 173

2..1 000 -> maxP was 73

So, It doesn't seem to grow quickly... If I knew a suitable formula... I could have written a quicker solution.

Anyway, I got AC (

http://acm.timus.ru/status.aspx?space=1&pos=867798). Details: 1356 Pascal Accepted 0.031 61 KB.

Please post anything you know on this topic. Are there better ways to find Goldbach partitions? Or are there better ideas on solving this problem?