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?
Puzzle: Can you find an elementary proof that every $n \gt 6$ can be represented as a sum of $O(\log n)$ distinct primes?
6
$\begingroup$
elementary-number-theory
prime-numbers
puzzle
1 Answers
8
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.
-
1@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 ;)) – 2011-10-01