# Given an even integer N, what is the minimum set of primes such that any even number x <= N can be expressed as the sum of two primes from the set?

Given an even integer N, what is the minimum set of primes such that any even number $x \leq N$ can be expressed as the sum of two primes in the set?

Goldbach's conjecture said Every even integer greater than 2 can be expressed as the sum of two primes. http://en.wikipedia.org/wiki/Goldbach's_conjecture

But think from the other way, it seems like we don't need that many primes in order to express every even number as the sum of two primes.

For example, there are 168 primes for $N=1000$, but using only 58 of them we can already express every even number as the sum of two primes: 2, 3, 5, 7, 13, 19, 23, 31, 37, 43, 47, 53, 61, 79, 83, 109, 113, 101, 131, 139, 157, 167, 199, 107, 211, 251, 281, 269, 283, 307, 313, 337, 293, 401, 421, 383, 439, 449, 431, 457, 491, 509, 523, 569, 601, 461, 643, 683, 673, 691, 743, 769, 761, 811, 863, 881, 929, 883

For $N=10000$, I found there only need 236 primes out of 1229: 2, 3, 5, 7, 13, 19, 23, 31, 37, 43, 47, 53, 61, 79, 83, 109, 113, 101, 131, 139, 157, 167, 199, 107, 211, 251, 281, 269, 283, 307, 313, 337, 293, 401, 421, 383, 439, 449, 431, 457, 491, 509, 523, 569, 601, 461, 643, 683, 673, 691, 743, 769, 761, 811, 863, 881, 929, 883, 983, 1013, 1031, 1063, 1069, 1097, 1103, 1129, 1151, 1163, 1181, 1237, 1229, 1307, 1327, 1399, 1381, 1367, 1459, 1511, 1489, 1559, 1567, 1637, 1699, 1787, 1811, 1709, 1831, 1879, 1931, 1901, 1951, 1973, 2063, 2081, 2099, 2161, 2153, 2243, 2273, 2287, 2207, 2309, 2381, 2411, 2417, 2377, 2473, 2503, 2593, 2663, 2671, 2621, 2731, 2819, 2843, 2861, 2969, 2971, 3011, 3049, 3119, 3137, 3187, 3299, 3373, 3319, 3461, 3541, 3533, 3583, 3631, 3623, 3709, 3761, 3779, 3793, 3833, 3923, 4021, 4073, 4091, 4111, 4133, 4177, 4241, 4259, 4273, 4337, 4339, 4357, 4363, 4523, 4621, 4657, 4703, 4721, 4729, 4813, 4861, 4943, 4973, 5099, 5153, 5119, 5209, 5303, 5351, 5347, 5393, 5443, 5521, 5573, 5581, 5693, 5701, 5743, 5903, 5923, 6053, 6037, 6203, 6277, 6287, 6473, 6469, 6529, 6569, 6607, 6581, 6653, 6659, 6719, 6781, 6841, 6863, 7039, 7121, 7129, 7177, 7253, 7351, 7417, 7517, 7523, 7703, 7691, 7741, 7823, 7879, 7951, 8123, 8101, 8111, 8243, 8269, 8039, 8291, 8443, 8537, 8681, 8747, 8783, 8819, 8849, 8839, 8933, 9091, 9187, 9241, 9323, 9419, 9349, 9551, 9547, 9803, 9883

All I can see is the lower bound of the size of necessary prime set is $\sqrt{N}$, the expected number of primes is $N/log(N)$, of course the later is much larger.

What is the law behind this? I'm not an expert in number theory, but just curious.

It is reasonable to believe that there is a constant $c$ such that that there exists a set of prime numbers containing at most $c \sqrt{x \log x}$ elements below $x$ such that each even number is the sum of two primes from this set. So the (lower) bound of $\sqrt{x}$ you mentioned is likely not too far away from the truth.

More specifically Granville showed (Theorem 2 in Refinements of Goldbach's conjecture, and the generalized Riemann hypothesis, Funct. Approx. Comment. Math. Volume 37, Number 1 (2007), 159-173) that this is true assuming a strong form of the Goldbach conjecture, namely that there is a positive constant $d$ such that each even number $n \gt 2$ has more than $d n/ (\log n)^2$ representations as a sum of two primes.

Essentially this came already up before on this site see Thin subbases for the primes? where among other things Mark Lewko also mentions this result.

• I'm looking at the review of Granville's paper at MR, and it looks like where you have $c\sqrt x\log x$ it should be $c\sqrt{x\log x}$. May 24, 2013 at 1:47
• @Gerry Myerson: thank you, yes, this was a typo (which I fixed in parallel with your comment). As additional general remark: the paper is freely available on the page I link to.
– user9072
May 24, 2013 at 2:02
• Thank you quid, I know such kind of problem must have been studied long time ago, the related works you provide are great! (although as a computer science researcher I'm not sure if I can fully understand it:) May 24, 2013 at 7:02
• @unknown: You are welcome!
– user9072
May 24, 2013 at 10:17