# Are the first 1,000 prime numbers enough to build every Goldbach number up to 9 digits long?

I'm writing a basic computer program in which one of my requirements is to find the smallest pair of prime numbers that make up a Goldbach number (up to 9 digits long, non-inclusive).

The user inputs any positive even number and I want the program to check if the summing parts are primes, but I want to maximize space so I want to only the smallest list of consecutive primes to check.

pretty much I want to know what are the fewest number of primes I need to check? The first 1000? the first 2000?

-
Your question is unclear. I take it by a "Goldbach number" you mean what most of us call an "even number." If $2n=p+q$ then the smaller $p$ is, the bigger $q$ is, so it's not clear what it means for one pair $(p,q)$ to be smaller than another $(p',q')$ with the same sum. Perhaps you are asking how big the smaller prime can be? – Gerry Myerson Apr 10 '12 at 12:10
@Gerry: I had exactly the same reaction, but the Wikipedia article starts by defining a "Goldbach number" to be "a number that can be expressed as the sum of two odd primes". It seems a bit wasteful to define a term that is most likely co-extensive with "even number greater than $4$" -- it might have made more sense to define a Goldbach number as an even number that cannot be thus expressed; then the Goldbach conjecture could be expressed as the problem of the existence of Goldbach numbers greater than $4$. – joriki Apr 10 '12 at 12:21
@joriki, I take your point. But as OP is only going up to 9 digits, "Goldbach number" is co-extensive with "even number greater than 4". – Gerry Myerson Apr 10 '12 at 12:57

278 primes suffice; no primes greater than 1789 are needed for numbers below 1,847,133,842.

With 1000 primes you could go up to 121,005,022,304,007,024.

-
How do you know? – Gerry Myerson Apr 11 '12 at 5:30
OEIS, maybe the same sequence (A025018) as you happened to list? – Charles Apr 11 '12 at 12:59

http://oeis.org/A025018 gives "Numbers n such that least prime in Goldbach partition of n increases," and begins, 4, 6, 12, 30, 98, 220, 308, 556, 992, 2642, 5372, 7426, 43532, 54244, 63274, 113672, 128168, 194428, 194470, 413572, 503222, 1077422, 3526958, 3807404, 10759922, 24106882, 27789878, 37998938, 60119912, 113632822, 187852862, 335070838.

http://oeis.org/A025019 gives "Smallest prime in Goldbach partition of A025018," and begins, 2, 3, 5, 7, 19, 23, 31, 47, 73, 103, 139, 173, 211, 233, 293, 313, 331, 359, 383, 389, 523, 601, 727, 751, 829, 929, 997, 1039, 1093, 1163, 1321, 1427, 1583, 1789, 1861, 1877, 1879, 2029, 2089, 2803, 3061, 3163, 3457, 3463, 3529, 3613, 3769, 3917, 4003, 4027, 4057.

So, for example, looking at the 5th entry in each list, the smallest prime $p$ such that $98=p+q$ and $q$ is prime is $p=19$, and a prime smaller than 19 will work for $2n\lt98$.

So you can use these lists and the references given at the site to work out how big the smallest prime might have to be for $2n$ up to a given value. If that's what you are asking about.

-

Suppose the plan is to take a smaller prime from the given list, and to test the primality of the remaining difference by trial division. Then we would need a list of primes that extends roughly to the square root of one billion ($10^9$). That is, the list would need to go up to the prime 31607 (the largest prime less than the square root of one billion).

According to the Prime Pages at utm.edu, "There are 3,401 primes less than or equal to 31,607." So if I understood your plan, you need a list of 3,400 primes (we will drop 2 as a prime because we will work only with odd primes).

Added: Of course typically for smallish trial division like we consider here, it's not horribly inefficient just to generate the superset of odd divisors consisting of $k \equiv 1,5 \mod 6$ on the fly. So perhaps the question is what list of primes is need to guarantee the smaller prime of a "minimal Goldbach partition" is there (see @GerryMyerson).

There's a paper by Granville, te Riele, and van de Lune (1989) that conjectures the smaller prime needed to partition n is bounded above by a constant times $(\ln n)^2 \ln \ln n$. Computational searching by Richstein (2000) showed that up to $n = 10^{14}$ the constant can be taken as 1.603, which would imply we only need a list of primes up to 2081, the 312th odd prime.

That's a far shorter list than one to be used for trial divisors as well.

-
Tomás Oliveira e Silva has greatly extended the search for Goldbach partitions: a 40,000-fold increase, to $4\cdot10^{18}.$ The 1.6023... bound still holds in this range. – Charles Jun 16 '12 at 23:26