# 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