I'm interested in all natural numbers, that are the sum of pariwise different prime numbers. For example 10 is such a number, since

$10 = 7 + 3$

My suspicion is that almost every natural number is the sum of pairwise different prime numbers. Actually by my pen & paper calculations, I did not find a natural number larger than 6 that is not such a sum, but I did not calculate much, so maybe there are even small numbers that are not a sum of pairwise different primes.

So my questions are these:

Is there any natural number larger than 6, which is not the sum of pairwise different primes? If not, any idea how to prove this?

And what's about the natural numbers, that are the sum of at least n natural prime numbers, with $n \in \mathbb{N}$? Is there any knowledge about these numbers?

Regards, S. M. Roch

Edit: I'm sorry, I forgot to say for my first question, that I also accept the sum of not only two prime numbers. So for example

$20 = 11 + 7 + 2$

is also such a sum, and for every prime number the number is its sum itself.

  • 1
    $\begingroup$ $11$ isn't such a sum. Or did you ask specifically about even numbers? $\endgroup$ – Arthur Aug 11 '16 at 22:22
  • 2
    $\begingroup$ The idea that all even natural numbers can be written as 2 primes is one of the most famous conjectures in mathematics, the Goldbach Conjecture. $\endgroup$ – Zestylemonzi Aug 11 '16 at 22:24
  • $\begingroup$ @Zestylemonzi the Goldbach Conjecture only deals with even numbers and allows the sum of any two prime numbers. On topic: every uneven number $2k+1$ can be written as the sum of two prime numbers $p\neq q$ if and only if $2k-1$ is prime. In this case we have $(2k-1)+2=2k+1$. Otherwise we will need to find two prime numbers with neither of them being two, thus they will be uneven and their sum can never be an uneven number. $\endgroup$ – Hirshy Aug 11 '16 at 22:29
  • 1
    $\begingroup$ If Goldbach is true, every odd number $> 5$ is the sum of at most $3$ primes. $\endgroup$ – Robert Israel Aug 11 '16 at 22:40
  • $\begingroup$ Thank you for your comments. For my first question, I meant the sum of an arbitrary number of prime numbers. I'm sorry, I added this in the "Edit" paragraph now. $\endgroup$ – S. M. Roch Aug 11 '16 at 22:49

A sketch of a proof:

For sufficiently large $N$, the Prime Number Theorem guarantees a prime $p$ between $N/2$ and $N-6$, $N/2\lt p\lt N-6$. This implies $6\lt N-p\lt N/2\lt N$, so strong induction tells us $N-p$ is the sum of distinct primes, $N-p=p_1+p_2+\cdots+p_n$ with $p_1\lt p_2\lt\cdots\lt p_n$. But $N-p\lt N/2\lt p$ tells us these primes are all less than $p$. Thus $N=p_1+p_2+\cdots+p_n+p$ with $p_1\lt p_2\lt\cdots\lt p_n\lt p$.

Note, Bertrand's postulate, which guarantees a prime between $N/2$ and $N$, isn't quite good enough. E.g., the only primes between $17/2$ and $17$ are $11$ and $13$, and neither $17-11=6$ nor $17-13=4$ can be written as a sum of distinct primes.

  • $\begingroup$ This is exactly what I wanted. That's great. Thank you. $\endgroup$ – S. M. Roch Aug 11 '16 at 23:50

There are lots of numbers greater than $6$ that are not the sum of pairwise different primes, like all the odd primes greater than $5$ that are not the larger part of a twin prime pair. If $n$ is odd, then so is $n - 2$. Remember that two odd primes add up to an even number.

In the case of $11$, we see that $11 - 2 = 9$, $11 - 3 = 8$, $11 - 5 = 6$ and $11 - 7 = 4$. Clearly $9$ is the square of an odd prime, and the rest are even numbers other than $2$. Look at Sloane's A014092 for plenty more examples.

For even $n$, you're talking about the Goldbach conjecture, as the commenters have already mentioned. For odd $n$, there is what is sometimes called the "weak" Goldbach conjecture, that every sufficiently large odd $n$ can be represented as the sum of three odd prime numbers.

Mathematicians have been able to prove both versions of the Goldbach conjecture for some numbers so large they are almost beyond the reach of our computers. But that doesn't disprove the possibility that a counterexample could exist just a little beyond your computer's ability.


Let me prove that ANY natural number n>6 can be written as the sum of two integers greater than 1,each of the summands being relatively prime.

First note that if d divides two integers a and b,then d must also divide their difference a-b.Therefore consecutive numbers are always relatively prime.Likewise,if a and b are both odd with difference 2 or 4,then a and b are relatively prime.

Now let n be greater than 7.
If n is odd,then n has the form n=2k+1,where k>3 is an integer.Thus we write the sum n=k+(k+1)
If n is even,then n has the form n=2k,where k>4 is an integer
-if k is even,we write n=(k-1)+(k+1);
-if k is odd,we write n=(k-2)+(k+2).

So we proved that ANY natural number n>6 can be written as the sum of two integers greater than 1,each of the summands being relatively prime!

  • $\begingroup$ I am sorry if the answer is not plain(I don't know how to use this LaTex or ...) $\endgroup$ – Melina Jan 2 at 14:16
  • 1
    $\begingroup$ But the question was not about summands being relatively prime (that's trivial), but about them being prime. $\endgroup$ – Henrik Jan 2 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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