Mersenne: Goldbach's Conjecture

[Thomas Womack]

Ah, this is more fun than complaints about network administration ...

Goldbach's Conjecture states that every even number greater than 4 is the sum
of two primes. It hasn't been proved yet; the closest we've got is a result by
Chen using sieve theory which shows that every sufficiently large even number
can be written as the sum of a prime and a number with at most two prime
factors.

If you define r(n) as the number of ways n can be written as a sum of two
primes, we have r(250) = 14 [since 250 = 83 + 167 = 71 + 179 = 59 + 191 = 53 +
197 = 23 + 227 = 17 + 233 = 11 + 239, and we count each of those twice]; as
far as I know r(n) is very rarely 2, so Joel's comment about uniqueness is
unfortunately false.

We'd expect Goldbach's Conjecture to be true, since the probability of a
number around N being prime is roughly 1/log N, so (assuming all sorts of
false theorems about independence) the probability of both k and N-k being
prime is roughly 1/(log N)^2. So the probability of them *never* being both
prime is roughly (1-1/(log N)^2)^(N/2), since there are N/2 ways of picking k
and N-k. Now, this tends to zero very quickly with N.

In fact, we can do better; there are roughly x/log x primes less than x, and
roughly 1/log x of those will have x-p also prime, so we expect R(x) = x/(log
x)^2. As far as my tests have run, we never have R(x) < x/(log x)^2, let alone
R(x) = 0 which is what a counterexample to the Goldbach Conjecture would
entail.

I've ran a test for N<2^26, which took a night on a P2/233, and produced the
data graphed in http://users.ox.ac.uk/~mert0236/maths/goldbach.gif and
http://users.ox.ac.uk/~mert0236/maths/goldbach[2..4].gif. What I'm plotting
there is the probability density function of (R(x) log(x)^2)/x; you will
notice the pretty fractal structure, which I am at the moment utterly unable
to explain.

Nicolau wrote :
>   Given N, let f1(N) be the number of primes of the form 4n+1 which
>   are smaller than N, and f3(N) be the number of primes of the form
>   4n+3 which are smaller than N. Thus, f1(10) = 1 and f3(10) = 2.
>   Is it true that f1(N) <= f3(N) for all N?
>
>The answer is no, but I challenge you to find a counter-example.


The computationally harder problem is to have f1(N) being primes of form 3n+1
and f2(N) being primes of form 3n+2; f2 wins up to N=608981813029. For your f1
and f3, f1(N)=f3(N) for N around 26932, around 615868, around 12311564 ...

It's probably unwise to make large computational challenges on a list whose
members almost by definition are interested in maths and have fast computers.

Tom