It's known that there is always a prime between $n$ and $2n-7$ for all $n \ge 10$. Prove that, with the exception of $1$, $4$, and $6$, every natural number can be written as the sum of distinct primes.
Problem
Source:
Tags: induction, floor function
maxal
25.05.2007 03:24
For small $n$ the statement can be verified instantly. Proof by induction that every $n\geq 7$ can be written as the sum of distinct primes. For basic cases $n=7,8,\dots,20$ the statement trivially holds. For $n\geq 20$ suppose that the statement holds for all integers in the interval $[7,n-1].$ Let $p$ be prime in the interval $[\lfloor n/2\rfloor+1, 2\lfloor n/2\rfloor - 8].$ Then $n=p+(n-p)$ where $7\leq n-p< p.$ Applying induction to $n-p$ completes the proof.
Peter
15.12.2007 00:03
How does it follow they are distinct?
ZetaX
15.12.2007 00:14
He has shown that $ p>n-p \geq 7$, thus $ p$ does not occure in the decomposition of $ n-p$ and the ones summing to $ n-p$ are distinct by induction.