# Puzzle: Can you find an elementary proof that every $n \gt 6$ can be represented as a sum of $O(\log n)$ distinct primes?

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?

-

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.

-
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