Is every integer the sum of distinct prime numbers?
$begingroup$
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.
elementary-number-theory prime-numbers
$endgroup$
add a comment |
$begingroup$
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.
elementary-number-theory prime-numbers
$endgroup$
3
$begingroup$
Heard about Goldbach's Conjecture? Still not proven.
$endgroup$
– SchrodingersCat
Nov 18 '15 at 15:36
$begingroup$
Goldbach's conjecture? No one proved it yet.
$endgroup$
– Atvin
Nov 18 '15 at 15:37
$begingroup$
@whatever see weak Goldbach's conj.
$endgroup$
– martin
Nov 18 '15 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 manos
Nov 18 '15 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 Omielan
2 days ago
add a comment |
$begingroup$
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.
elementary-number-theory prime-numbers
$endgroup$
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.
elementary-number-theory prime-numbers
elementary-number-theory prime-numbers
edited Nov 18 '15 at 20:02
Solomonoff's Secret
3,65211233
3,65211233
asked Nov 18 '15 at 15:35


BPPBPP
2,166927
2,166927
3
$begingroup$
Heard about Goldbach's Conjecture? Still not proven.
$endgroup$
– SchrodingersCat
Nov 18 '15 at 15:36
$begingroup$
Goldbach's conjecture? No one proved it yet.
$endgroup$
– Atvin
Nov 18 '15 at 15:37
$begingroup$
@whatever see weak Goldbach's conj.
$endgroup$
– martin
Nov 18 '15 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 manos
Nov 18 '15 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 Omielan
2 days ago
add a comment |
3
$begingroup$
Heard about Goldbach's Conjecture? Still not proven.
$endgroup$
– SchrodingersCat
Nov 18 '15 at 15:36
$begingroup$
Goldbach's conjecture? No one proved it yet.
$endgroup$
– Atvin
Nov 18 '15 at 15:37
$begingroup$
@whatever see weak Goldbach's conj.
$endgroup$
– martin
Nov 18 '15 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 manos
Nov 18 '15 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 Omielan
2 days ago
3
3
$begingroup$
Heard about Goldbach's Conjecture? Still not proven.
$endgroup$
– SchrodingersCat
Nov 18 '15 at 15:36
$begingroup$
Heard about Goldbach's Conjecture? Still not proven.
$endgroup$
– SchrodingersCat
Nov 18 '15 at 15:36
$begingroup$
Goldbach's conjecture? No one proved it yet.
$endgroup$
– Atvin
Nov 18 '15 at 15:37
$begingroup$
Goldbach's conjecture? No one proved it yet.
$endgroup$
– Atvin
Nov 18 '15 at 15:37
$begingroup$
@whatever see weak Goldbach's conj.
$endgroup$
– martin
Nov 18 '15 at 15:37
$begingroup$
@whatever see weak Goldbach's conj.
$endgroup$
– martin
Nov 18 '15 at 15:37
1
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 manos
Nov 18 '15 at 15:38
$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 manos
Nov 18 '15 at 15:38
1
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 Omielan
2 days ago
$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 Omielan
2 days ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
By Bertrand's postulate, you can find a prime satisfying $lfloor n/2rfloor <p< n$. Proceed by induction.
$endgroup$
1
$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$
– Thomas Andrews
Nov 18 '15 at 15:55
2
$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$
– Thomas Andrews
Nov 18 '15 at 16:00
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$
– Thomas Andrews
Nov 18 '15 at 21:00
1
$begingroup$
And the linked Wikipedia article even mentions this explicitly in the subsection Consequences.
$endgroup$
– Jeppe Stig Nielsen
Nov 18 '15 at 21:36
1
$begingroup$
Would you consider integrating the content of your comments into your answer? Right now someone reading this answer needs to sift through the comments to find all the useful information. Thanks.
$endgroup$
– Najib Idrissi
Dec 1 '15 at 8:58
|
show 5 more comments
$begingroup$
Note that we can not write $2$ in required form.
Take any integer (say) $x$ with $3le x.$
Let $y$ be the largest prime strictly less than $x.$ If $x-yin Q$ we are already done.
Suppose $x-ynotin Q.$ Then, take the largest prime strictly less than $x-y.$
And continue this..
$endgroup$
$begingroup$
After I post my answer, I feel that, It would be easy to use strong induction than continue above process.
$endgroup$
– Bumblebee
Dec 1 '15 at 8:58
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1535354%2fis-every-integer-the-sum-of-distinct-prime-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
By Bertrand's postulate, you can find a prime satisfying $lfloor n/2rfloor <p< n$. Proceed by induction.
$endgroup$
1
$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$
– Thomas Andrews
Nov 18 '15 at 15:55
2
$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$
– Thomas Andrews
Nov 18 '15 at 16:00
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$
– Thomas Andrews
Nov 18 '15 at 21:00
1
$begingroup$
And the linked Wikipedia article even mentions this explicitly in the subsection Consequences.
$endgroup$
– Jeppe Stig Nielsen
Nov 18 '15 at 21:36
1
$begingroup$
Would you consider integrating the content of your comments into your answer? Right now someone reading this answer needs to sift through the comments to find all the useful information. Thanks.
$endgroup$
– Najib Idrissi
Dec 1 '15 at 8:58
|
show 5 more comments
$begingroup$
By Bertrand's postulate, you can find a prime satisfying $lfloor n/2rfloor <p< n$. Proceed by induction.
$endgroup$
1
$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$
– Thomas Andrews
Nov 18 '15 at 15:55
2
$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$
– Thomas Andrews
Nov 18 '15 at 16:00
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$
– Thomas Andrews
Nov 18 '15 at 21:00
1
$begingroup$
And the linked Wikipedia article even mentions this explicitly in the subsection Consequences.
$endgroup$
– Jeppe Stig Nielsen
Nov 18 '15 at 21:36
1
$begingroup$
Would you consider integrating the content of your comments into your answer? Right now someone reading this answer needs to sift through the comments to find all the useful information. Thanks.
$endgroup$
– Najib Idrissi
Dec 1 '15 at 8:58
|
show 5 more comments
$begingroup$
By Bertrand's postulate, you can find a prime satisfying $lfloor n/2rfloor <p< n$. Proceed by induction.
$endgroup$
By Bertrand's postulate, you can find a prime satisfying $lfloor n/2rfloor <p< n$. Proceed by induction.
answered Nov 18 '15 at 15:46


Thomas AndrewsThomas Andrews
131k12147298
131k12147298
1
$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$
– Thomas Andrews
Nov 18 '15 at 15:55
2
$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$
– Thomas Andrews
Nov 18 '15 at 16:00
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$
– Thomas Andrews
Nov 18 '15 at 21:00
1
$begingroup$
And the linked Wikipedia article even mentions this explicitly in the subsection Consequences.
$endgroup$
– Jeppe Stig Nielsen
Nov 18 '15 at 21:36
1
$begingroup$
Would you consider integrating the content of your comments into your answer? Right now someone reading this answer needs to sift through the comments to find all the useful information. Thanks.
$endgroup$
– Najib Idrissi
Dec 1 '15 at 8:58
|
show 5 more comments
1
$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$
– Thomas Andrews
Nov 18 '15 at 15:55
2
$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$
– Thomas Andrews
Nov 18 '15 at 16:00
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$
– Thomas Andrews
Nov 18 '15 at 21:00
1
$begingroup$
And the linked Wikipedia article even mentions this explicitly in the subsection Consequences.
$endgroup$
– Jeppe Stig Nielsen
Nov 18 '15 at 21:36
1
$begingroup$
Would you consider integrating the content of your comments into your answer? Right now someone reading this answer needs to sift through the comments to find all the useful information. Thanks.
$endgroup$
– Najib Idrissi
Dec 1 '15 at 8:58
1
1
$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$
– Thomas Andrews
Nov 18 '15 at 15:55
$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$
– Thomas Andrews
Nov 18 '15 at 15:55
2
2
$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$
– Thomas Andrews
Nov 18 '15 at 16:00
$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$
– Thomas Andrews
Nov 18 '15 at 16:00
2
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$
– Thomas Andrews
Nov 18 '15 at 21:00
$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$
– Thomas Andrews
Nov 18 '15 at 21:00
1
1
$begingroup$
And the linked Wikipedia article even mentions this explicitly in the subsection Consequences.
$endgroup$
– Jeppe Stig Nielsen
Nov 18 '15 at 21:36
$begingroup$
And the linked Wikipedia article even mentions this explicitly in the subsection Consequences.
$endgroup$
– Jeppe Stig Nielsen
Nov 18 '15 at 21:36
1
1
$begingroup$
Would you consider integrating the content of your comments into your answer? Right now someone reading this answer needs to sift through the comments to find all the useful information. Thanks.
$endgroup$
– Najib Idrissi
Dec 1 '15 at 8:58
$begingroup$
Would you consider integrating the content of your comments into your answer? Right now someone reading this answer needs to sift through the comments to find all the useful information. Thanks.
$endgroup$
– Najib Idrissi
Dec 1 '15 at 8:58
|
show 5 more comments
$begingroup$
Note that we can not write $2$ in required form.
Take any integer (say) $x$ with $3le x.$
Let $y$ be the largest prime strictly less than $x.$ If $x-yin Q$ we are already done.
Suppose $x-ynotin Q.$ Then, take the largest prime strictly less than $x-y.$
And continue this..
$endgroup$
$begingroup$
After I post my answer, I feel that, It would be easy to use strong induction than continue above process.
$endgroup$
– Bumblebee
Dec 1 '15 at 8:58
add a comment |
$begingroup$
Note that we can not write $2$ in required form.
Take any integer (say) $x$ with $3le x.$
Let $y$ be the largest prime strictly less than $x.$ If $x-yin Q$ we are already done.
Suppose $x-ynotin Q.$ Then, take the largest prime strictly less than $x-y.$
And continue this..
$endgroup$
$begingroup$
After I post my answer, I feel that, It would be easy to use strong induction than continue above process.
$endgroup$
– Bumblebee
Dec 1 '15 at 8:58
add a comment |
$begingroup$
Note that we can not write $2$ in required form.
Take any integer (say) $x$ with $3le x.$
Let $y$ be the largest prime strictly less than $x.$ If $x-yin Q$ we are already done.
Suppose $x-ynotin Q.$ Then, take the largest prime strictly less than $x-y.$
And continue this..
$endgroup$
Note that we can not write $2$ in required form.
Take any integer (say) $x$ with $3le x.$
Let $y$ be the largest prime strictly less than $x.$ If $x-yin Q$ we are already done.
Suppose $x-ynotin Q.$ Then, take the largest prime strictly less than $x-y.$
And continue this..
answered Dec 1 '15 at 8:57


BumblebeeBumblebee
9,74912551
9,74912551
$begingroup$
After I post my answer, I feel that, It would be easy to use strong induction than continue above process.
$endgroup$
– Bumblebee
Dec 1 '15 at 8:58
add a comment |
$begingroup$
After I post my answer, I feel that, It would be easy to use strong induction than continue above process.
$endgroup$
– Bumblebee
Dec 1 '15 at 8:58
$begingroup$
After I post my answer, I feel that, It would be easy to use strong induction than continue above process.
$endgroup$
– Bumblebee
Dec 1 '15 at 8:58
$begingroup$
After I post my answer, I feel that, It would be easy to use strong induction than continue above process.
$endgroup$
– Bumblebee
Dec 1 '15 at 8:58
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1535354%2fis-every-integer-the-sum-of-distinct-prime-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
$begingroup$
Heard about Goldbach's Conjecture? Still not proven.
$endgroup$
– SchrodingersCat
Nov 18 '15 at 15:36
$begingroup$
Goldbach's conjecture? No one proved it yet.
$endgroup$
– Atvin
Nov 18 '15 at 15:37
$begingroup$
@whatever see weak Goldbach's conj.
$endgroup$
– martin
Nov 18 '15 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 manos
Nov 18 '15 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 Omielan
2 days ago