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

Question

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?

Answer 1

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.