Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can you find an elementary proof that every $n \gt 6$ can be represented as a sum of $O(\log n)$ distinct primes? For example, $11 = 11$, $12 = 5 + 7$, $13 = 2 + 11$, $14 = 2 + 5 + 7$. On the other hand, 6 cannot be represented as the sum of distinct primes. Vinogradov's theorem implies this but I am expecting a simple demonstration. I can prove the statement to my own satisfaction but I think it is an interesting problem and I am wondering what is the simplest and most rigorous approach?

share|cite|improve this question
up vote 8 down vote accepted

By Bertrand's postulate, there is a prime between $n/2$ and $n$. Pick the largest such prime and recurse. The number goes down by a factor of at least $2$ in each step, so we can take at most $O(\log n)$ rounds.

share|cite|improve this answer
Problem: what if you keep reducing $n$ recursively and, say, end up with $6$? This occurs when you have consecutive sexy primes, e.g. $29-23=6$. – anon Sep 30 '11 at 4:57
@anon: The proof can be fixed by using Bertand's postulate to pick a prime between $(n-6)/2$ and $n-6$. – TonyK Sep 30 '11 at 10:27
Very concise explanation. – Dan Brumleve Oct 1 '11 at 23:35
@Dan Thanks. Concise, yes :), but I am afraid it is actually a little far from rigorous. I am still trying to fill the gap anon mentioned. TonyK's fix seems to work fine, but I am not yet sure that all cases are taken care of. (I wish you had posed the problem without the restriction that the primes are distinct ;)) – Srivatsan Oct 1 '11 at 23:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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