Let $\Bbb{P}$ be the set of prime numbers and $Q=\Bbb{P}\cup\{1\}$. Is it true that every natural numbers ($\neq 0$) is the sum of distinct elements of $Q$? I tried from $1$ to $60$ and it seems true.
$\begingroup$
$\endgroup$
5
-
4$\begingroup$ Heard about Goldbach's Conjecture? Still not proven. $\endgroup$– SchrodingersCatCommented Nov 18, 2015 at 15:36
-
$\begingroup$ Goldbach's conjecture? No one proved it yet. $\endgroup$– AtvinCommented Nov 18, 2015 at 15:37
-
$\begingroup$ @whatever see weak Goldbach's conj. $\endgroup$– martinCommented Nov 18, 2015 at 15:37
-
1$\begingroup$ If every even integer can be expressed as a sum of $2$ prime numbers, then every integer can be expressed as a sum of at most $3$ prime numbers. The "if" part of this statement has yet to be proven. $\endgroup$– barak manosCommented Nov 18, 2015 at 15:38
-
1$\begingroup$ FYI, what you are asking about is an example of a Complete sequence. The linked Wikipedia article provides a definition, conditions, several examples (starting with the primes & 1), and applications where this may be used. $\endgroup$– John OmielanCommented Apr 4, 2019 at 17:29
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
10
By [Bertrand's postulate][1], you can find a prime satisfying $\lfloor n/2\rfloor <p< n$. Proceed by induction.
Update with fuller proof
Prove it for $n\leq 6$ or so.
If true for all $n\leq m$ with $m\geq 6,$ then by Betrand's postulate, there is a prime $$\left\lceil \frac{m+1}2\right\rceil <p<2\left\lceil \frac{m+1}2\right\rceil.$$ But $2\left\lceil \frac{m+1}2\right\rceil\leq m+2,$ so $p\leq m+1.$
If $p=m+1,$ then we are done, since $m+1$ is the sum of one prime.
If $p<m+1,$ then $0<m+1-p<\frac{m+1}{2}<p,$ so $m+1-p$ can be written as a sum of distinct elements of $\mathbb P\cup\{1\},$ and since $m+1-p<p,$ those distinct elements do not include $p,$ so $m+1$ is the sum of distinct elements of $\mathbb P\cup\{1\}.$
You can probably show that for $n$ large, all $n$ can be expressed as a sum of distinct primes, not including $1.$ You'll need something slightly stronger than Bertrand. It might be the case that the only numbers requiring $1$ are $4$ and $6.$
If so, you'll need to find an $N_0$ that for $N\geq N_0$ is a prime between $N$ and $2N-6.$ Then you need to start by showing it is true for $6<n\leq N_0,$ and then you get the same induction. Looks like $N_0=9$ might work, but proving the variant of Bertrand might be tricky.
answered Nov 18, 2015 at 15:46
-
1$\begingroup$ Once you've found $p$ meeting this condition, you know that $n-p<p$, so you apply the same step to $n'=n-p$. The key is that you are making $n-p$ small enough that any sum for $n-p$ cannot include $p$. $\endgroup$ Commented Nov 18, 2015 at 15:51
-
3$\begingroup$ So, for example, if you want to solve $n=64$, find a prime between $32$ and $64$, say, $p_1=37$. Then solve for $64-37=27$ - take $p_2=17$ between $27/2$ and $27$. Then solve for $27-17=10$ with $p_3=7$ between $10/2$ and $10$. Now you are down to $10-7=3$ which is prime, so you are done. So $64=3+7+17+37$. (We could have obviously gone faster by picking bigger primes at each step.) $\endgroup$ Commented Nov 18, 2015 at 15:55
-
3$\begingroup$ Sure, I left out a big step - which is the initial range of the induction. You have to treat the small values on a case-by-case basis. Not meant to be a complete answer. @RamirodelaVega $\endgroup$ Commented Nov 18, 2015 at 16:00
-
1$\begingroup$ 1, 2, 3, 4, 6, 11 are not the sum of distinct primes. Summing primes up to 13 you get all other sums from 12 to 34. Adding 23 gets 35 to 57. Adding 43 gives 55 to 100. Adding 89 gives 101 to 189. And so on. $\endgroup$ Commented Nov 18, 2015 at 20:59
-
2$\begingroup$ $2,3,11$ are the sum of sets of one prime. $6=5+1$ - OP specifically includes $1$ in the set, and $11=7+3+1$. @gnasher729 $\endgroup$ Commented Nov 18, 2015 at 21:00
$\begingroup$
$\endgroup$
1
Note that we can not write $2$ in required form.
Take any integer (say) $x$ with $3\le x.$
Let $y$ be the largest prime strictly less than $x.$ If $x-y\in Q$ we are already done.
Suppose $x-y\not\in Q.$ Then, take the largest prime strictly less than $x-y.$
And continue this..
-
$\begingroup$ After I post my answer, I feel that, It would be easy to use strong induction than continue above process. $\endgroup$ Commented Dec 1, 2015 at 8:58