Mixing
Finding if a number is prime by looking at the sum of their digits
$begingroup$
Take a number $N = overline{abcdef...}$ where $a, b, c, d,e,dots$ are the digits of $N$.
Let $k$ be the sum of those digits :
$a+b+c+d+e+... = k$
If $k$ is any of ${1, 2, 4, 5, 7, 8 }$ then $N$ is prime. Otherwise it is not a prime.
Example: $N = 17$ and $k = 1+ 7 = 8,$ Therefore $N$ is prime.
Now, I want to know the following:
1) Is my guess is correct, and if so how can I prove it mathematically ?
2) If I am wrong, where I am wrong ?
Regards-Gandhi,
Thanks!
number-theory elementary-number-theory prime-numbers proof-verification
edited Oct 4 '14 at 14:35
Hippalectryon
4,38622656
asked Oct 4 '14 at 14:09
number theorynumber theory
305
$endgroup$
|
show 7 more comments
$begingroup$
Take a number $N = overline{abcdef...}$ where $a, b, c, d,e,dots$ are the digits of $N$.
Let $k$ be the sum of those digits :
$a+b+c+d+e+... = k$
If $k$ is any of ${1, 2, 4, 5, 7, 8 }$ then $N$ is prime. Otherwise it is not a prime.
Example: $N = 17$ and $k = 1+ 7 = 8,$ Therefore $N$ is prime.
Now, I want to know the following:
1) Is my guess is correct, and if so how can I prove it mathematically ?
2) If I am wrong, where I am wrong ?
Regards-Gandhi,
Thanks!
number-theory elementary-number-theory prime-numbers proof-verification
edited Oct 4 '14 at 14:35
Hippalectryon
4,38622656
asked Oct 4 '14 at 14:09
number theorynumber theory
305
$endgroup$
$begingroup$
$1275563$ is prime, but $1+2+7+5+5+6+3=29$ which is different from $1,2,4,5,7,8$. Did you mean that we add the digits on and on until the sum is a one digit number ?
$endgroup$
– Hippalectryon
Oct 4 '14 at 14:15
$begingroup$
$N = 26$ has $2+6 = 8$.
$endgroup$
– Daniel Fischer
Oct 4 '14 at 14:16
3
$begingroup$
N=3 is prime...
$endgroup$
– Exodd
Oct 4 '14 at 14:19
1
$begingroup$
22, 202, 2002, 20002, 200002, ... are all counter-examples
$endgroup$
– Exodd
Oct 4 '14 at 14:31
1
$begingroup$
You are correct that if $N>3$ is prime, then the repeated digit sum cannot be $3,6,9$. But the reverse is false. You basically are just testing for divisibility by $3$.
$endgroup$
– Thomas Andrews
Oct 4 '14 at 15:11
|
show 7 more comments
$begingroup$
Take a number $N = overline{abcdef...}$ where $a, b, c, d,e,dots$ are the digits of $N$.
Let $k$ be the sum of those digits :
$a+b+c+d+e+... = k$
If $k$ is any of ${1, 2, 4, 5, 7, 8 }$ then $N$ is prime. Otherwise it is not a prime.
Example: $N = 17$ and $k = 1+ 7 = 8,$ Therefore $N$ is prime.
Now, I want to know the following:
1) Is my guess is correct, and if so how can I prove it mathematically ?
2) If I am wrong, where I am wrong ?
Regards-Gandhi,
Thanks!
number-theory elementary-number-theory prime-numbers proof-verification
edited Oct 4 '14 at 14:35
Hippalectryon
4,38622656
asked Oct 4 '14 at 14:09
number theorynumber theory
305
$endgroup$
Take a number $N = overline{abcdef...}$ where $a, b, c, d,e,dots$ are the digits of $N$.
Let $k$ be the sum of those digits :
$a+b+c+d+e+... = k$
If $k$ is any of ${1, 2, 4, 5, 7, 8 }$ then $N$ is prime. Otherwise it is not a prime.
Example: $N = 17$ and $k = 1+ 7 = 8,$ Therefore $N$ is prime.
Now, I want to know the following:
1) Is my guess is correct, and if so how can I prove it mathematically ?
2) If I am wrong, where I am wrong ?
Regards-Gandhi,
Thanks!
number-theory elementary-number-theory prime-numbers proof-verification
number-theory elementary-number-theory prime-numbers proof-verification
edited Oct 4 '14 at 14:35
Hippalectryon
4,38622656
asked Oct 4 '14 at 14:09
number theorynumber theory
305
edited Oct 4 '14 at 14:35
Hippalectryon
4,38622656
asked Oct 4 '14 at 14:09
number theorynumber theory
305
edited Oct 4 '14 at 14:35
Hippalectryon
4,38622656
edited Oct 4 '14 at 14:35
Hippalectryon
4,38622656
edited Oct 4 '14 at 14:35
Hippalectryon
4,38622656
4,38622656
asked Oct 4 '14 at 14:09
number theorynumber theory
305
asked Oct 4 '14 at 14:09
number theorynumber theory
305
asked Oct 4 '14 at 14:09
number theorynumber theory
305
305
$begingroup$
$1275563$ is prime, but $1+2+7+5+5+6+3=29$ which is different from $1,2,4,5,7,8$. Did you mean that we add the digits on and on until the sum is a one digit number ?
$endgroup$
– Hippalectryon
Oct 4 '14 at 14:15
$begingroup$
$N = 26$ has $2+6 = 8$.
$endgroup$
– Daniel Fischer
Oct 4 '14 at 14:16
3
$begingroup$
N=3 is prime...
$endgroup$
– Exodd
Oct 4 '14 at 14:19
1
$begingroup$
22, 202, 2002, 20002, 200002, ... are all counter-examples
$endgroup$
– Exodd
Oct 4 '14 at 14:31
1
$begingroup$
You are correct that if $N>3$ is prime, then the repeated digit sum cannot be $3,6,9$. But the reverse is false. You basically are just testing for divisibility by $3$.
$endgroup$
– Thomas Andrews
Oct 4 '14 at 15:11
|
show 7 more comments
$begingroup$
$1275563$ is prime, but $1+2+7+5+5+6+3=29$ which is different from $1,2,4,5,7,8$. Did you mean that we add the digits on and on until the sum is a one digit number ?
$endgroup$
– Hippalectryon
Oct 4 '14 at 14:15
$begingroup$
$N = 26$ has $2+6 = 8$.
$endgroup$
– Daniel Fischer
Oct 4 '14 at 14:16
3
$begingroup$
N=3 is prime...
$endgroup$
– Exodd
Oct 4 '14 at 14:19
1
$begingroup$
22, 202, 2002, 20002, 200002, ... are all counter-examples
$endgroup$
– Exodd
Oct 4 '14 at 14:31
1
$begingroup$
You are correct that if $N>3$ is prime, then the repeated digit sum cannot be $3,6,9$. But the reverse is false. You basically are just testing for divisibility by $3$.
$endgroup$
– Thomas Andrews
Oct 4 '14 at 15:11
$begingroup$
$1275563$ is prime, but $1+2+7+5+5+6+3=29$ which is different from $1,2,4,5,7,8$. Did you mean that we add the digits on and on until the sum is a one digit number ?
$endgroup$
– Hippalectryon
Oct 4 '14 at 14:15
$begingroup$
$1275563$ is prime, but $1+2+7+5+5+6+3=29$ which is different from $1,2,4,5,7,8$. Did you mean that we add the digits on and on until the sum is a one digit number ?
$endgroup$
– Hippalectryon
Oct 4 '14 at 14:15
$begingroup$
$N = 26$ has $2+6 = 8$.
$endgroup$
– Daniel Fischer
Oct 4 '14 at 14:16
$begingroup$
$N = 26$ has $2+6 = 8$.
$endgroup$
– Daniel Fischer
Oct 4 '14 at 14:16
3
3
$begingroup$
N=3 is prime...
$endgroup$
– Exodd
Oct 4 '14 at 14:19
$begingroup$
N=3 is prime...
$endgroup$
– Exodd
Oct 4 '14 at 14:19
1
1
$begingroup$
22, 202, 2002, 20002, 200002, ... are all counter-examples
$endgroup$
– Exodd
Oct 4 '14 at 14:31
$begingroup$
22, 202, 2002, 20002, 200002, ... are all counter-examples
$endgroup$
– Exodd
Oct 4 '14 at 14:31
1
1
$begingroup$
You are correct that if $N>3$ is prime, then the repeated digit sum cannot be $3,6,9$. But the reverse is false. You basically are just testing for divisibility by $3$.
$endgroup$
– Thomas Andrews
Oct 4 '14 at 15:11
$begingroup$
You are correct that if $N>3$ is prime, then the repeated digit sum cannot be $3,6,9$. But the reverse is false. You basically are just testing for divisibility by $3$.
$endgroup$
– Thomas Andrews
Oct 4 '14 at 15:11
|
show 7 more comments
3 Answers
3
active
oldest
votes
$begingroup$
Any number is congruent with the sum of its digits modulo 9.
Therefore, if the sum of the digits is 3,6 or 0 $pmod{9}$ the number is divisible by $3$. And in this case, the number is either $3$ or composite.
If the sum of the digits is $1,2,4,5,7,8 pmod{9}$ the number could be prime.
There are infinitely many numbers of this form which are not prime, and Dirichlet Theorem tells us that there are also infinitely many numbers of this form which are prime.
answered Oct 4 '14 at 15:39
N. S.N. S.
105k7115210
$endgroup$
add a comment |
$begingroup$
The digit sum operation you describe is invariant modulo 9.
The 5-digit number $abcde = a 10^4 + b 10^3 + c 10^2 + d 10 + e$. Since $10 = 9 + 1 equiv 1 mod 9$, you can see that $abcde equiv a + b + c + d + e mod 9$.
So if a number's digit sum is divisible by 3 that means the number itself is also divisible by 3. No primes (other than 3) are divisible by 3. So you have a way to prove a number is not prime, but not a way to prove that it is prime.
answered Oct 4 '14 at 14:33
NovaDenizenNovaDenizen
3,503718
$endgroup$
add a comment |
$begingroup$
Asymptotically, the fraction of all numbers which are composite is 1, and your method predicts 1/3. This means it's wrong asymptotically about 2/3 of the time.
Up to 10^25, there are 176846309399143769411680 primes. Your method predicts that 1 of these is composite and the rest are prime. There are also 9823153690600856230588319 composites up to 10^25. Of these it predicts that 3333333333333333333333332 are composite and 6489820357267522897254987 are prime, for a total of 3510179642732477102745012 or about 35% correct.
answered Oct 6 '14 at 4:07
CharlesCharles
24k452116
$endgroup$
add a comment |
Your Answer
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%2f957978%2ffinding-if-a-number-is-prime-by-looking-at-the-sum-of-their-digits%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Any number is congruent with the sum of its digits modulo 9.
Therefore, if the sum of the digits is 3,6 or 0 $pmod{9}$ the number is divisible by $3$. And in this case, the number is either $3$ or composite.
If the sum of the digits is $1,2,4,5,7,8 pmod{9}$ the number could be prime.
There are infinitely many numbers of this form which are not prime, and Dirichlet Theorem tells us that there are also infinitely many numbers of this form which are prime.
answered Oct 4 '14 at 15:39
N. S.N. S.
105k7115210
$endgroup$
add a comment |
$begingroup$
Any number is congruent with the sum of its digits modulo 9.
Therefore, if the sum of the digits is 3,6 or 0 $pmod{9}$ the number is divisible by $3$. And in this case, the number is either $3$ or composite.
If the sum of the digits is $1,2,4,5,7,8 pmod{9}$ the number could be prime.
There are infinitely many numbers of this form which are not prime, and Dirichlet Theorem tells us that there are also infinitely many numbers of this form which are prime.
answered Oct 4 '14 at 15:39
N. S.N. S.
105k7115210
$endgroup$
add a comment |
$begingroup$
Any number is congruent with the sum of its digits modulo 9.
Therefore, if the sum of the digits is 3,6 or 0 $pmod{9}$ the number is divisible by $3$. And in this case, the number is either $3$ or composite.
If the sum of the digits is $1,2,4,5,7,8 pmod{9}$ the number could be prime.
There are infinitely many numbers of this form which are not prime, and Dirichlet Theorem tells us that there are also infinitely many numbers of this form which are prime.
answered Oct 4 '14 at 15:39
N. S.N. S.
105k7115210
$endgroup$
Any number is congruent with the sum of its digits modulo 9.
Therefore, if the sum of the digits is 3,6 or 0 $pmod{9}$ the number is divisible by $3$. And in this case, the number is either $3$ or composite.
If the sum of the digits is $1,2,4,5,7,8 pmod{9}$ the number could be prime.
There are infinitely many numbers of this form which are not prime, and Dirichlet Theorem tells us that there are also infinitely many numbers of this form which are prime.
answered Oct 4 '14 at 15:39
N. S.N. S.
105k7115210
answered Oct 4 '14 at 15:39
N. S.N. S.
105k7115210
answered Oct 4 '14 at 15:39
N. S.N. S.
105k7115210
answered Oct 4 '14 at 15:39
N. S.N. S.
105k7115210
105k7115210
add a comment |
add a comment |
$begingroup$
The digit sum operation you describe is invariant modulo 9.
The 5-digit number $abcde = a 10^4 + b 10^3 + c 10^2 + d 10 + e$. Since $10 = 9 + 1 equiv 1 mod 9$, you can see that $abcde equiv a + b + c + d + e mod 9$.
So if a number's digit sum is divisible by 3 that means the number itself is also divisible by 3. No primes (other than 3) are divisible by 3. So you have a way to prove a number is not prime, but not a way to prove that it is prime.
answered Oct 4 '14 at 14:33
NovaDenizenNovaDenizen
3,503718
$endgroup$
add a comment |
$begingroup$
The digit sum operation you describe is invariant modulo 9.
The 5-digit number $abcde = a 10^4 + b 10^3 + c 10^2 + d 10 + e$. Since $10 = 9 + 1 equiv 1 mod 9$, you can see that $abcde equiv a + b + c + d + e mod 9$.
So if a number's digit sum is divisible by 3 that means the number itself is also divisible by 3. No primes (other than 3) are divisible by 3. So you have a way to prove a number is not prime, but not a way to prove that it is prime.
answered Oct 4 '14 at 14:33
NovaDenizenNovaDenizen
3,503718
$endgroup$
add a comment |
$begingroup$
The digit sum operation you describe is invariant modulo 9.
The 5-digit number $abcde = a 10^4 + b 10^3 + c 10^2 + d 10 + e$. Since $10 = 9 + 1 equiv 1 mod 9$, you can see that $abcde equiv a + b + c + d + e mod 9$.
So if a number's digit sum is divisible by 3 that means the number itself is also divisible by 3. No primes (other than 3) are divisible by 3. So you have a way to prove a number is not prime, but not a way to prove that it is prime.
answered Oct 4 '14 at 14:33
NovaDenizenNovaDenizen
3,503718
$endgroup$
The digit sum operation you describe is invariant modulo 9.
The 5-digit number $abcde = a 10^4 + b 10^3 + c 10^2 + d 10 + e$. Since $10 = 9 + 1 equiv 1 mod 9$, you can see that $abcde equiv a + b + c + d + e mod 9$.
So if a number's digit sum is divisible by 3 that means the number itself is also divisible by 3. No primes (other than 3) are divisible by 3. So you have a way to prove a number is not prime, but not a way to prove that it is prime.
answered Oct 4 '14 at 14:33
NovaDenizenNovaDenizen
3,503718
edited Oct 4 '14 at 15:32
answered Oct 4 '14 at 14:33
NovaDenizenNovaDenizen
3,503718
answered Oct 4 '14 at 14:33
NovaDenizenNovaDenizen
3,503718
answered Oct 4 '14 at 14:33
NovaDenizenNovaDenizen
3,503718
3,503718
add a comment |
add a comment |
$begingroup$
Asymptotically, the fraction of all numbers which are composite is 1, and your method predicts 1/3. This means it's wrong asymptotically about 2/3 of the time.
Up to 10^25, there are 176846309399143769411680 primes. Your method predicts that 1 of these is composite and the rest are prime. There are also 9823153690600856230588319 composites up to 10^25. Of these it predicts that 3333333333333333333333332 are composite and 6489820357267522897254987 are prime, for a total of 3510179642732477102745012 or about 35% correct.
answered Oct 6 '14 at 4:07
CharlesCharles
24k452116
$endgroup$
add a comment |
$begingroup$
Asymptotically, the fraction of all numbers which are composite is 1, and your method predicts 1/3. This means it's wrong asymptotically about 2/3 of the time.
Up to 10^25, there are 176846309399143769411680 primes. Your method predicts that 1 of these is composite and the rest are prime. There are also 9823153690600856230588319 composites up to 10^25. Of these it predicts that 3333333333333333333333332 are composite and 6489820357267522897254987 are prime, for a total of 3510179642732477102745012 or about 35% correct.
answered Oct 6 '14 at 4:07
CharlesCharles
24k452116
$endgroup$
add a comment |
$begingroup$
Asymptotically, the fraction of all numbers which are composite is 1, and your method predicts 1/3. This means it's wrong asymptotically about 2/3 of the time.
Up to 10^25, there are 176846309399143769411680 primes. Your method predicts that 1 of these is composite and the rest are prime. There are also 9823153690600856230588319 composites up to 10^25. Of these it predicts that 3333333333333333333333332 are composite and 6489820357267522897254987 are prime, for a total of 3510179642732477102745012 or about 35% correct.
answered Oct 6 '14 at 4:07
CharlesCharles
24k452116
$endgroup$
Asymptotically, the fraction of all numbers which are composite is 1, and your method predicts 1/3. This means it's wrong asymptotically about 2/3 of the time.
Up to 10^25, there are 176846309399143769411680 primes. Your method predicts that 1 of these is composite and the rest are prime. There are also 9823153690600856230588319 composites up to 10^25. Of these it predicts that 3333333333333333333333332 are composite and 6489820357267522897254987 are prime, for a total of 3510179642732477102745012 or about 35% correct.
answered Oct 6 '14 at 4:07
CharlesCharles
24k452116
answered Oct 6 '14 at 4:07
CharlesCharles
24k452116
answered Oct 6 '14 at 4:07
CharlesCharles
24k452116
answered Oct 6 '14 at 4:07
CharlesCharles
24k452116
24k452116
add a comment |
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%2f957978%2ffinding-if-a-number-is-prime-by-looking-at-the-sum-of-their-digits%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
$begingroup$
$1275563$ is prime, but $1+2+7+5+5+6+3=29$ which is different from $1,2,4,5,7,8$. Did you mean that we add the digits on and on until the sum is a one digit number ?
$endgroup$
– Hippalectryon
Oct 4 '14 at 14:15
$begingroup$
$N = 26$ has $2+6 = 8$.
$endgroup$
– Daniel Fischer
Oct 4 '14 at 14:16
3
$begingroup$
N=3 is prime...
$endgroup$
– Exodd
Oct 4 '14 at 14:19
1
$begingroup$
22, 202, 2002, 20002, 200002, ... are all counter-examples
$endgroup$
– Exodd
Oct 4 '14 at 14:31
1
$begingroup$
You are correct that if $N>3$ is prime, then the repeated digit sum cannot be $3,6,9$. But the reverse is false. You basically are just testing for divisibility by $3$.
$endgroup$
– Thomas Andrews
Oct 4 '14 at 15:11