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?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
Here's how it works:
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.