Let $S_x$ be the set of finite sums of prime numbers $\geq x$. In other words, let $S_x$ be the submonoid of $(\mathbf{Z}_{\geq 0},+)$ generated by the set $\mathcal{P}_{\geq x}$ of prime numbers $\geq x$.

It is easy to see that $S_x$ contains every sufficiently large integer. This follows from the classical fact that given two coprime integers $a$ and $b$, every sufficiently large integer, in fact every integer $\geq (a-1)(b-1)$, is of the form $ma+nb$ for some $m, n \in \mathbf{Z}_{\geq 0}$. See for example this page.

Let $N_x$ be the largest integer which is not in $S_x$.

Examples :

If $x=2$ then $S_2 = \{0\} \cup \mathbf{N}_{\geq 2}$ so that $N_2=1$.

If $x=3$ then $S_3 = \{0,3\} \cup \mathbf{N}_{\geq 5}$ so that $N_3=4$.

By definition, we have $N_x \geq x-1$ (in fact parity considerations imply that $N_x \geq 2x-2$ for $x \geq 3$).

On the other hand, given that there are at least two primes in the interval $[x,2x]$, the above classical fact implies that $N_x \ll x^2$.

What is the asymptotic behaviour of $N_x$ as $x \to \infty$ ?

  • $\begingroup$ Interesting question! This is essentially Sloane's A180306, but it does not contain any information on the asymptotics. $\endgroup$
    – Charles
    Apr 3, 2012 at 15:22
  • $\begingroup$ @Charles : Thanks for the reference to Sloane's database. @Mark : I don't really know. I suspect that the upper bound I gave is much too high, but I don't know what to expect since I'm not a specialist in additive number theory. $\endgroup$ Apr 3, 2012 at 16:10
  • 2
    $\begingroup$ Lemma 1 of Erdos's 1974 paper with Benkoski "On weird and pseudoperfect numbers" is: There is an absolute constant $c$ such that every integer $m > c p_k$ is the distinct sum of primes not less than $p_k$. (Here $p_k$ is the $k$th prime, in the usual order.) No proof is given. "The lemma is probably well known and, in any case, easily follows by Brun's method." $\endgroup$
    – Anonymous
    Apr 4, 2012 at 2:08
  • $\begingroup$ @Anonymous : Thanks for the reference! It would be interesting to make $c$ explicit. $\endgroup$ Apr 4, 2012 at 8:53
  • $\begingroup$ In view of the answers below indicating the link with Goldbach's conjecture, which is out of reach, I would accept any answer showing that $N_x \ll x$. $\endgroup$ Apr 4, 2012 at 9:21

3 Answers 3


According to "The three primes theorem with almost equal summands" by Baker and Harman, every large odd $N$ is a sum of three primes each of size $\sim N/3$. (In fact, within $N^{4/7}$ of $N/3$-- this is much closer than we need, so we could use weaker results of earlier authors, if preferred.)

For odd $N$, this gives $N$ as a sum of three primes, each at least $\sim N/3$. If $N$ is even, take a prime $p$ of size $\sim N/4$ (which exists by the prime number theorem), and write $N-p$ as a sum of three primes of size about $N/4$. So we get $N$ as a sum of four primes at least $\sim N/4$.

  • $\begingroup$ Thanks! This result indeed shows that $N_x/x$ is bounded (and in fact $\operatorname{limsup} N_x/x \leq 4$). $\endgroup$ Apr 6, 2012 at 9:17

(Edited according to the comments below)

In his article titled 'Sums of Distinct Primes', Kløve conjectured, on the basis of computational evidence, that $\displaystyle \lim_{x \rightarrow \infty} \dfrac{N_x}{x} = 3$. This would imply the binary Goldbach conjecture (for large enough $x$) in the following way: if every integer larger than $(3 + \epsilon)x$ can be written as sum of primes, where those primes are all larger than $x$, then, in particular, every even number between $(3 + \epsilon)x$ and $4x$ can be written as a sum of two primes.

  • $\begingroup$ @Woett: In that paper, the word "prime" does not appear. $\endgroup$
    – user6976
    Apr 3, 2012 at 16:24
  • $\begingroup$ Hmm, maybe I understand the question wrong. Please read page 56 of the article of Erdos and Graham (page 52 of this pdf: math.ucsd.edu/~ronspubs/80_11_number_theory.pdf) $\endgroup$
    – Woett
    Apr 3, 2012 at 16:30
  • 2
    $\begingroup$ @Woett: Yes, Kløve, Torleiv Sums of distinct primes. Nordisk Mat. Tidskr. 21 (1973), 138–140. According to Math Reviews he conjectured there that the limit is 3. The review does not mention Goldbach. The paper is not on-line, unfortunately. $\endgroup$
    – user6976
    Apr 3, 2012 at 17:53
  • 1
    $\begingroup$ Does Vinogradov result that every sufficiently large odd number is a sum of three primes imply that the limit is at most 5 (or at least $< \infty$)? Vinogradov does not claim that his primes are all of approximately the same size, but perhaps his method can be adapted to produce such a result. $\endgroup$
    – user6976
    Apr 3, 2012 at 18:18
  • 1
    $\begingroup$ @François: No, since not requiring the primes to be distinct can only make the limit lower, but the limit has to be at least 3 (there is an odd composite in $[3n-5,3n)$). $\endgroup$ Apr 4, 2012 at 10:18

Just to spell it out, If Golbach's conjecture is false, then at least once $N(x)>4x$, but that seems extremely unlikely. It is certain that $N(x)>3x$ infinitely often, but there is every reason to believe that $N(x)<(3+\epsilon)x$ with finitely many exceptions. If so, then we could equivalently define $N_x$ as the largest odd integer which is neither prime nor a sum of $3$ primes all at least $x$.

it will frequently happen that the next prime after $p$ is at least $p+8.$ In these cases we can write $3p$ as a sum of primes at least $x=p$ however at least one of the odd numbers $3p+2,3p+4,3p+6$ is not itself prime and hence not a sum of primes all greater than $x=p.$ This establishes that $N(x)>3x$ infinitely often.

There is no proof that every even integer is a sum of two primes. Were there a counter-example, $E$, it would need to be a sum of at least 4 primes and hence furnish an example of $N(x)>4x$ where $x$ is $\frac{E}{4}.$ However there is every reason to believe the stronger statement that for every $\epsilon \gt 0$ there is an $M(\epsilon)$ such that $2m$ is a sum of two primes, both larger than $m(1-\epsilon)$ for all $m \gt M(\epsilon).$ If so, then $N(x)<(3+\epsilon)x$ provided that $x$ is reasonably larger $\frac{M(\epsilon)}{1-\epsilon}.$

  • 4
    $\begingroup$ Using $x = k! + 1$, we can even show that $\limsup_{x \rightarrow \infty} N(x) - 3x = \infty$. In fact, using an estimate of Rankin on large prime gaps, we should get $N(x) - 3x > c\log x \log \log x \log \log \log \log x (\log \log \log x)^{-2}$ infinitely often. $\endgroup$
    – Woett
    Apr 4, 2012 at 4:15
  • $\begingroup$ However, does not rule out the possibility that for every $\epsilon \gt 0$ we have $\limsup_{x \to \infty}N(x)-(3+\epsilon)x=-\infty$ $\endgroup$ Apr 4, 2012 at 4:33
  • $\begingroup$ Oh, of course not! Perhaps even $N(x) < 3x + x^{\epsilon}$ for large $x$. But this should be really far from what can be proven with current methods :) $\endgroup$
    – Woett
    Apr 4, 2012 at 4:41
  • $\begingroup$ True. With current methods we can not prove Golbach's conjecture so we do not know that $N(x) \lt 4x$ is true, although we believe it is. Were I foolish I would predict $(3+c_1/\ln{x})x \lt N(x) \lt (3+c_2/\ln{x})x.$ $\endgroup$ Apr 4, 2012 at 5:08
  • $\begingroup$ Thanks Aaron for your answer. I believe your argument shows that for any odd $x$ which is not prime, we have $N(x) \geq 3x$, since $3x$ cannot be written as a sum of primes $\geq x$. $\endgroup$ Apr 4, 2012 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.