Mixing
a big number that is obviously prime?
$begingroup$
I once heard it asserted that $91$ is the smallest composite number that is not obviously composite. The reasoning was that any composite number divisible by $2$, $3$, or $5$ is obviously composite, and the only composite numbers less than $91$ that are not divisible by $2$, $3$, or $5$ are $49$ and $77$, and it's obvious that those are obviously composite.
I'm going to go out on a limb and wildly guess that $577$ might be the largest prime number that is as obviously prime, or at least as quickly and easily seen to be prime as it is.
It's obviously not divisible by $2$, $3$, or $5$, and $7$ and $11$ are instantly rejected since subtraction of $77$ from this number leaves $500$, and $13$ is rejected since this number plus $13$ is $590$ so we've reduced it to thinking about the two-digit number $59$, and likewise subtracting $17$ from this number leaves $560$, and $56$ is not divisible by $17$, and subtracting $7$ leaves $570$ and $57$ is divisible by $19$, so we reject $19$. Finally, adding $23$ gives $600$, so we reject that, and there's no occasion to go higher than $23$ since $23+1 = 24=lfloorsqrt{577}rfloor$.
So staring at it for ten seconds gives you the answer without writing anything or doing any divisions or looking at factorizations of nearby numbers that don't reduce instantly to two-digit problems. It's not unusual to reject a bunch of primes by doing this, but rejecting all of them by instantaneous reduction to one- or two-digit problems I don't recall seeing before.
Are there any bigger primes than $577$ where this is so quick and simple?
prime-numbers arithmetic recreational-mathematics mental-arithmetic
asked May 23 '12 at 16:56
Michael HardyMichael Hardy
1
$endgroup$
add a comment |
$begingroup$
I once heard it asserted that $91$ is the smallest composite number that is not obviously composite. The reasoning was that any composite number divisible by $2$, $3$, or $5$ is obviously composite, and the only composite numbers less than $91$ that are not divisible by $2$, $3$, or $5$ are $49$ and $77$, and it's obvious that those are obviously composite.
I'm going to go out on a limb and wildly guess that $577$ might be the largest prime number that is as obviously prime, or at least as quickly and easily seen to be prime as it is.
It's obviously not divisible by $2$, $3$, or $5$, and $7$ and $11$ are instantly rejected since subtraction of $77$ from this number leaves $500$, and $13$ is rejected since this number plus $13$ is $590$ so we've reduced it to thinking about the two-digit number $59$, and likewise subtracting $17$ from this number leaves $560$, and $56$ is not divisible by $17$, and subtracting $7$ leaves $570$ and $57$ is divisible by $19$, so we reject $19$. Finally, adding $23$ gives $600$, so we reject that, and there's no occasion to go higher than $23$ since $23+1 = 24=lfloorsqrt{577}rfloor$.
So staring at it for ten seconds gives you the answer without writing anything or doing any divisions or looking at factorizations of nearby numbers that don't reduce instantly to two-digit problems. It's not unusual to reject a bunch of primes by doing this, but rejecting all of them by instantaneous reduction to one- or two-digit problems I don't recall seeing before.
Are there any bigger primes than $577$ where this is so quick and simple?
prime-numbers arithmetic recreational-mathematics mental-arithmetic
asked May 23 '12 at 16:56
Michael HardyMichael Hardy
1
$endgroup$
$begingroup$
When I read the title first thing that came to my mind was primality certificate. It would be more obvious to me if the number was given with a certificate. Anyway, great question ;-)
$endgroup$
– dtldarek
May 23 '12 at 21:48
$begingroup$
I believe that $lfloorsqrt{577}rfloor = 24$...
$endgroup$
– u8y7541
May 13 '17 at 21:51
$begingroup$
@u8y7541 : Fixed. $23$ is not the "floor" of $sqrt{577}$ but it is the "prime floor" of $sqrt{577}. qquad$
$endgroup$
– Michael Hardy
May 14 '17 at 16:19
add a comment |
$begingroup$
I once heard it asserted that $91$ is the smallest composite number that is not obviously composite. The reasoning was that any composite number divisible by $2$, $3$, or $5$ is obviously composite, and the only composite numbers less than $91$ that are not divisible by $2$, $3$, or $5$ are $49$ and $77$, and it's obvious that those are obviously composite.
I'm going to go out on a limb and wildly guess that $577$ might be the largest prime number that is as obviously prime, or at least as quickly and easily seen to be prime as it is.
It's obviously not divisible by $2$, $3$, or $5$, and $7$ and $11$ are instantly rejected since subtraction of $77$ from this number leaves $500$, and $13$ is rejected since this number plus $13$ is $590$ so we've reduced it to thinking about the two-digit number $59$, and likewise subtracting $17$ from this number leaves $560$, and $56$ is not divisible by $17$, and subtracting $7$ leaves $570$ and $57$ is divisible by $19$, so we reject $19$. Finally, adding $23$ gives $600$, so we reject that, and there's no occasion to go higher than $23$ since $23+1 = 24=lfloorsqrt{577}rfloor$.
So staring at it for ten seconds gives you the answer without writing anything or doing any divisions or looking at factorizations of nearby numbers that don't reduce instantly to two-digit problems. It's not unusual to reject a bunch of primes by doing this, but rejecting all of them by instantaneous reduction to one- or two-digit problems I don't recall seeing before.
Are there any bigger primes than $577$ where this is so quick and simple?
prime-numbers arithmetic recreational-mathematics mental-arithmetic
asked May 23 '12 at 16:56
Michael HardyMichael Hardy
1
$endgroup$
I once heard it asserted that $91$ is the smallest composite number that is not obviously composite. The reasoning was that any composite number divisible by $2$, $3$, or $5$ is obviously composite, and the only composite numbers less than $91$ that are not divisible by $2$, $3$, or $5$ are $49$ and $77$, and it's obvious that those are obviously composite.
I'm going to go out on a limb and wildly guess that $577$ might be the largest prime number that is as obviously prime, or at least as quickly and easily seen to be prime as it is.
It's obviously not divisible by $2$, $3$, or $5$, and $7$ and $11$ are instantly rejected since subtraction of $77$ from this number leaves $500$, and $13$ is rejected since this number plus $13$ is $590$ so we've reduced it to thinking about the two-digit number $59$, and likewise subtracting $17$ from this number leaves $560$, and $56$ is not divisible by $17$, and subtracting $7$ leaves $570$ and $57$ is divisible by $19$, so we reject $19$. Finally, adding $23$ gives $600$, so we reject that, and there's no occasion to go higher than $23$ since $23+1 = 24=lfloorsqrt{577}rfloor$.
So staring at it for ten seconds gives you the answer without writing anything or doing any divisions or looking at factorizations of nearby numbers that don't reduce instantly to two-digit problems. It's not unusual to reject a bunch of primes by doing this, but rejecting all of them by instantaneous reduction to one- or two-digit problems I don't recall seeing before.
Are there any bigger primes than $577$ where this is so quick and simple?
prime-numbers arithmetic recreational-mathematics mental-arithmetic
prime-numbers arithmetic recreational-mathematics mental-arithmetic
asked May 23 '12 at 16:56
Michael HardyMichael Hardy
1
asked May 23 '12 at 16:56
Michael HardyMichael Hardy
1
edited May 14 '17 at 16:18
Michael Hardy
asked May 23 '12 at 16:56
Michael HardyMichael Hardy
1
asked May 23 '12 at 16:56
Michael HardyMichael Hardy
1
asked May 23 '12 at 16:56
Michael HardyMichael Hardy
1
1
$begingroup$
When I read the title first thing that came to my mind was primality certificate. It would be more obvious to me if the number was given with a certificate. Anyway, great question ;-)
$endgroup$
– dtldarek
May 23 '12 at 21:48
$begingroup$
I believe that $lfloorsqrt{577}rfloor = 24$...
$endgroup$
– u8y7541
May 13 '17 at 21:51
$begingroup$
@u8y7541 : Fixed. $23$ is not the "floor" of $sqrt{577}$ but it is the "prime floor" of $sqrt{577}. qquad$
$endgroup$
– Michael Hardy
May 14 '17 at 16:19
add a comment |
$begingroup$
When I read the title first thing that came to my mind was primality certificate. It would be more obvious to me if the number was given with a certificate. Anyway, great question ;-)
$endgroup$
– dtldarek
May 23 '12 at 21:48
$begingroup$
I believe that $lfloorsqrt{577}rfloor = 24$...
$endgroup$
– u8y7541
May 13 '17 at 21:51
$begingroup$
@u8y7541 : Fixed. $23$ is not the "floor" of $sqrt{577}$ but it is the "prime floor" of $sqrt{577}. qquad$
$endgroup$
– Michael Hardy
May 14 '17 at 16:19
$begingroup$
When I read the title first thing that came to my mind was primality certificate. It would be more obvious to me if the number was given with a certificate. Anyway, great question ;-)
$endgroup$
– dtldarek
May 23 '12 at 21:48
$begingroup$
When I read the title first thing that came to my mind was primality certificate. It would be more obvious to me if the number was given with a certificate. Anyway, great question ;-)
$endgroup$
– dtldarek
May 23 '12 at 21:48
$begingroup$
I believe that $lfloorsqrt{577}rfloor = 24$...
$endgroup$
– u8y7541
May 13 '17 at 21:51
$begingroup$
I believe that $lfloorsqrt{577}rfloor = 24$...
$endgroup$
– u8y7541
May 13 '17 at 21:51
$begingroup$
@u8y7541 : Fixed. $23$ is not the "floor" of $sqrt{577}$ but it is the "prime floor" of $sqrt{577}. qquad$
$endgroup$
– Michael Hardy
May 14 '17 at 16:19
$begingroup$
@u8y7541 : Fixed. $23$ is not the "floor" of $sqrt{577}$ but it is the "prime floor" of $sqrt{577}. qquad$
$endgroup$
– Michael Hardy
May 14 '17 at 16:19
add a comment |
6 Answers
6
active
oldest
votes
$begingroup$
${}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}$
$endgroup$
9
$begingroup$
I don't consider this humour, I consider this a very lame attempt at humour. If you want to get an upvote from me you'll have to do better than that.
$endgroup$
– Rudy the Reindeer
May 24 '12 at 15:08
13
$begingroup$
It answers the question, since its not very clear what is a 'big number'
$endgroup$
– TROLLHUNTER
May 24 '12 at 15:15
21
$begingroup$
All threes are equal, but some are more equal than others.
$endgroup$
– Gerry Myerson
May 25 '12 at 1:35
5
$begingroup$
This is a big numeral, not a big number. :p
$endgroup$
– Hurkyl
Dec 1 '12 at 19:08
4
$begingroup$
@Hurkyl, this is from a book called The Phantom Tollbooth, en.wikipedia.org/wiki/The_Phantom_Tollbooth . In the Numbers Mine, Milo asks for the biggest number and is shown a huge 3. See books.google.com/…
$endgroup$
– Will Jagy
Dec 1 '12 at 19:31
|
show 4 more comments
$begingroup$
We have that $677$ is obviously not divisible by $2, 3$, or $5$. Subtracting $77$ leaves $600$ which is not divisible by $7$ or $11$. Adding $13$ to it leaves $690$ which also reduces it to thinking about the two digit number $69$. Likewise subtracting $17$ from this number leaves $660$, and $66$ is not divisible by $17$, and subtracting $57$ leaves $620$ and $62$ is not divisible by $19$, so we reject $19$. Finally, adding $23$ gives $700$, so we reject that, and there's no occasion to go higher than $23$ since we have that $lfloorsqrt{677}rfloor = 26$ so we need only check up to $23$.
As a bonus let's try $977$ which is prime. We have that $977$ is obviously not divisible by $2, 3$, or $5$. Subtracting $77$ leaves $900$ which is not divisible by $7$ or $11$, which also reduces it to thinking about the two digit number $90$ which is neither divisible by $7$ or $11$. Adding $13$ to it leaves $990$ which also reduces it to thinking about the two digit number $99$. Likewise subtracting $17$ from this number leaves $960$, and $96$ is not divisible by $17$, and subtracting $57$ leaves $920$ and $92$ is not divisible by $19$, so we reject $19$. Adding $23$ gives $1000$, so we reject that. Subtracting $87$ leaves $890$ and $89$ is not divisible by $29$, so we reject $29$. Finally, adding $93$ to $977$ gives us $1070$ and $107$ is not divisible by $31$ so we reject $31$ as well. Since we have that $lfloorsqrt{977}rfloor = 31$, we need only check up to $31$ so we are done.
edited May 14 '17 at 16:25
Michael Hardy
1
answered May 23 '12 at 17:24
EugeneEugene
5,03112362
$endgroup$
$begingroup$
Maybe this is a part of a general pattern, and maybe one of many such patterns. I hadn't noticed one so simple before.
$endgroup$
– Michael Hardy
May 23 '12 at 17:31
$begingroup$
I suspect it is. I'm just going to conjecture that this will work for all primes 77 mod 100. I'll think about it more when I'm less busy.
$endgroup$
– Eugene
May 23 '12 at 17:36
5
$begingroup$
Are you suggesting that $100000000000003177$ is obviously prime?
$endgroup$
– Robert Israel
May 23 '12 at 17:46
$begingroup$
Fair enough. If it gets too large I suppose it is a problem.
$endgroup$
– Eugene
May 23 '12 at 17:52
2
$begingroup$
My conjecture was for primes 77 mod 100 though rather than an if and only if statement i.e. if n is a prime 77 mod 100 that is not too big, then we can perform a procedure similar to the ones above.
$endgroup$
– Eugene
May 24 '12 at 5:53
|
show 5 more comments
$begingroup$
This quicker primality test can be done for numbers in any arithmetic progression. For example, rather than $577$ let's consider more generally numbers of the form $rm:m = 10:!n !-! 3.:$ Because we are considering only $1/10$ of the integers, we can effectively reduce an Eratosthenes sieve primality test on $rm:m:$ to a sieve on an integer roughly $1/10,$'th the size of $rm:m,:$ namely $rm:n.:$ Indeed, we have
Theorem $ $ If the positive integer $rm m: =: 10:!n!-!3 < 841 = 29^2:$ then
$$rm 10:!n!-!3 is primeiff 3nmid n, : 7nmid n!-!1, : 11nmid n!+!3,: 13nmid n!+!1,: 17nmid n!-!2,: 19nmid n!-!6,: 23nmid n!+!2 $$
Proof $ $ Since $rm:m < 29^2,:$ if it is composite it must be divisible by a prime $rm:p < 29,:$ hence $rm:p le 23.:$ Consider, e.g. $rm:p = 13:|:10:!n!-!3iff 13:|:10:!n!-!3!+!13 = 10(n!+!1)iff 13:|:n!+!1,:$ etc. $ $ QED
Your example $rm:577 = 10cdot 58 - 3:$ so the above primality test amounts to checking if any of the above $7$ primes divide $rm: 58pm k,:$ for $rm:kle 6,:$ which can be done very quickly mentally, as you did.
answered May 23 '12 at 21:07
Bill DubuqueBill Dubuque
213k29195654
$endgroup$
add a comment |
$begingroup$
There is a very nice paper about this, Guy, Lacampagne, and Selfridge, Primes at a glance, Mathematics of Computation Vol. 48, No. 177, Jan., 1987, pages 183 to 202. I think that back issues of this journal are freely available at the American Mathematical Society website.
There is a follow-up paper by Agoh, Erdos, and Granville, Primes at a (somewhat lengthy) glance, The American Mathematical Monthly Vol. 104, No. 10, Dec., 1997, pages 943 to 945, but I'm pretty sure that one's behind a paywall if you don't connect from a subscriber.
EDIT: Link to Primes at a glance mentioned above.
edited Nov 22 '14 at 9:50
Daniel R
2,49532035
answered May 24 '12 at 1:37
Gerry MyersonGerry Myerson
147k8151304
$endgroup$
add a comment |
$begingroup$
can't resist following the pattern: 877. Additionally, need to test for 29 (but trivial)
answered May 23 '12 at 17:53
karakfakarakfa
2,025811
$endgroup$
2
$begingroup$
$29 mid 87$, so that reduces to two digits.
$endgroup$
– Michael Hardy
May 23 '12 at 20:47
1
$begingroup$
or subtracting 87 from 877 you'll get 790 which is not divisible by 29.
$endgroup$
– Keivan
May 23 '12 at 23:59
add a comment |
$begingroup$
How quick is quick enough?
$n=1601$. Let $x=39$. $1601=40^2+1=40x+41=x^2+x+41$ which, as is well known, is prime for integer $0leqslant x<40$.
$n=2081$ obviously has the form $x^2+5y^2$ ($x=9, y=20$) so every prime factor of $n$ has an even tens-digit. Clearly not 3.
- 7: $2100-n=19$ and $7nmid 19$.
- 23: $2300-n=219$; $230-219=11$ and $23nmid 11$.
- 29: $n+29=2110$; $211+29=240$ and $29nmid 24$.
- 41: $n-41=2040$; $5cdot 41=205$ so $41nmid 204$.
- 43: $43^2$ ends in 9; $43cdot 47=45^2-2^2=2021ne n$ and any other composite with smallest prime factor $geqslant 43$ would be $>n$.
answered Jan 27 at 18:17
Rosie FRosie F
1,379416
$endgroup$
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%2f148852%2fa-big-number-that-is-obviously-prime%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
6 Answers
6
active
oldest
votes
6 Answers
6
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
${}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}$
$endgroup$
9
$begingroup$
I don't consider this humour, I consider this a very lame attempt at humour. If you want to get an upvote from me you'll have to do better than that.
$endgroup$
– Rudy the Reindeer
May 24 '12 at 15:08
13
$begingroup$
It answers the question, since its not very clear what is a 'big number'
$endgroup$
– TROLLHUNTER
May 24 '12 at 15:15
21
$begingroup$
All threes are equal, but some are more equal than others.
$endgroup$
– Gerry Myerson
May 25 '12 at 1:35
5
$begingroup$
This is a big numeral, not a big number. :p
$endgroup$
– Hurkyl
Dec 1 '12 at 19:08
4
$begingroup$
@Hurkyl, this is from a book called The Phantom Tollbooth, en.wikipedia.org/wiki/The_Phantom_Tollbooth . In the Numbers Mine, Milo asks for the biggest number and is shown a huge 3. See books.google.com/…
$endgroup$
– Will Jagy
Dec 1 '12 at 19:31
|
show 4 more comments
$begingroup$
${}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}$
$endgroup$
9
$begingroup$
I don't consider this humour, I consider this a very lame attempt at humour. If you want to get an upvote from me you'll have to do better than that.
$endgroup$
– Rudy the Reindeer
May 24 '12 at 15:08
13
$begingroup$
It answers the question, since its not very clear what is a 'big number'
$endgroup$
– TROLLHUNTER
May 24 '12 at 15:15
21
$begingroup$
All threes are equal, but some are more equal than others.
$endgroup$
– Gerry Myerson
May 25 '12 at 1:35
5
$begingroup$
This is a big numeral, not a big number. :p
$endgroup$
– Hurkyl
Dec 1 '12 at 19:08
4
$begingroup$
@Hurkyl, this is from a book called The Phantom Tollbooth, en.wikipedia.org/wiki/The_Phantom_Tollbooth . In the Numbers Mine, Milo asks for the biggest number and is shown a huge 3. See books.google.com/…
$endgroup$
– Will Jagy
Dec 1 '12 at 19:31
|
show 4 more comments
$begingroup$
${}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}$
$endgroup$
${}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}$
edited May 24 '12 at 14:53
community wiki
2 revs
Will Jagy
9
$begingroup$
I don't consider this humour, I consider this a very lame attempt at humour. If you want to get an upvote from me you'll have to do better than that.
$endgroup$
– Rudy the Reindeer
May 24 '12 at 15:08
13
$begingroup$
It answers the question, since its not very clear what is a 'big number'
$endgroup$
– TROLLHUNTER
May 24 '12 at 15:15
21
$begingroup$
All threes are equal, but some are more equal than others.
$endgroup$
– Gerry Myerson
May 25 '12 at 1:35
5
$begingroup$
This is a big numeral, not a big number. :p
$endgroup$
– Hurkyl
Dec 1 '12 at 19:08
4
$begingroup$
@Hurkyl, this is from a book called The Phantom Tollbooth, en.wikipedia.org/wiki/The_Phantom_Tollbooth . In the Numbers Mine, Milo asks for the biggest number and is shown a huge 3. See books.google.com/…
$endgroup$
– Will Jagy
Dec 1 '12 at 19:31
|
show 4 more comments
9
$begingroup$
I don't consider this humour, I consider this a very lame attempt at humour. If you want to get an upvote from me you'll have to do better than that.
$endgroup$
– Rudy the Reindeer
May 24 '12 at 15:08
13
$begingroup$
It answers the question, since its not very clear what is a 'big number'
$endgroup$
– TROLLHUNTER
May 24 '12 at 15:15
21
$begingroup$
All threes are equal, but some are more equal than others.
$endgroup$
– Gerry Myerson
May 25 '12 at 1:35
5
$begingroup$
This is a big numeral, not a big number. :p
$endgroup$
– Hurkyl
Dec 1 '12 at 19:08
4
$begingroup$
@Hurkyl, this is from a book called The Phantom Tollbooth, en.wikipedia.org/wiki/The_Phantom_Tollbooth . In the Numbers Mine, Milo asks for the biggest number and is shown a huge 3. See books.google.com/…
$endgroup$
– Will Jagy
Dec 1 '12 at 19:31
9
9
$begingroup$
I don't consider this humour, I consider this a very lame attempt at humour. If you want to get an upvote from me you'll have to do better than that.
$endgroup$
– Rudy the Reindeer
May 24 '12 at 15:08
$begingroup$
I don't consider this humour, I consider this a very lame attempt at humour. If you want to get an upvote from me you'll have to do better than that.
$endgroup$
– Rudy the Reindeer
May 24 '12 at 15:08
13
13
$begingroup$
It answers the question, since its not very clear what is a 'big number'
$endgroup$
– TROLLHUNTER
May 24 '12 at 15:15
$begingroup$
It answers the question, since its not very clear what is a 'big number'
$endgroup$
– TROLLHUNTER
May 24 '12 at 15:15
21
21
$begingroup$
All threes are equal, but some are more equal than others.
$endgroup$
– Gerry Myerson
May 25 '12 at 1:35
$begingroup$
All threes are equal, but some are more equal than others.
$endgroup$
– Gerry Myerson
May 25 '12 at 1:35
5
5
$begingroup$
This is a big numeral, not a big number. :p
$endgroup$
– Hurkyl
Dec 1 '12 at 19:08
$begingroup$
This is a big numeral, not a big number. :p
$endgroup$
– Hurkyl
Dec 1 '12 at 19:08
4
4
$begingroup$
@Hurkyl, this is from a book called The Phantom Tollbooth, en.wikipedia.org/wiki/The_Phantom_Tollbooth . In the Numbers Mine, Milo asks for the biggest number and is shown a huge 3. See books.google.com/…
$endgroup$
– Will Jagy
Dec 1 '12 at 19:31
$begingroup$
@Hurkyl, this is from a book called The Phantom Tollbooth, en.wikipedia.org/wiki/The_Phantom_Tollbooth . In the Numbers Mine, Milo asks for the biggest number and is shown a huge 3. See books.google.com/…
$endgroup$
– Will Jagy
Dec 1 '12 at 19:31
|
show 4 more comments
$begingroup$
We have that $677$ is obviously not divisible by $2, 3$, or $5$. Subtracting $77$ leaves $600$ which is not divisible by $7$ or $11$. Adding $13$ to it leaves $690$ which also reduces it to thinking about the two digit number $69$. Likewise subtracting $17$ from this number leaves $660$, and $66$ is not divisible by $17$, and subtracting $57$ leaves $620$ and $62$ is not divisible by $19$, so we reject $19$. Finally, adding $23$ gives $700$, so we reject that, and there's no occasion to go higher than $23$ since we have that $lfloorsqrt{677}rfloor = 26$ so we need only check up to $23$.
As a bonus let's try $977$ which is prime. We have that $977$ is obviously not divisible by $2, 3$, or $5$. Subtracting $77$ leaves $900$ which is not divisible by $7$ or $11$, which also reduces it to thinking about the two digit number $90$ which is neither divisible by $7$ or $11$. Adding $13$ to it leaves $990$ which also reduces it to thinking about the two digit number $99$. Likewise subtracting $17$ from this number leaves $960$, and $96$ is not divisible by $17$, and subtracting $57$ leaves $920$ and $92$ is not divisible by $19$, so we reject $19$. Adding $23$ gives $1000$, so we reject that. Subtracting $87$ leaves $890$ and $89$ is not divisible by $29$, so we reject $29$. Finally, adding $93$ to $977$ gives us $1070$ and $107$ is not divisible by $31$ so we reject $31$ as well. Since we have that $lfloorsqrt{977}rfloor = 31$, we need only check up to $31$ so we are done.
edited May 14 '17 at 16:25
Michael Hardy
1
answered May 23 '12 at 17:24
EugeneEugene
5,03112362
$endgroup$
$begingroup$
Maybe this is a part of a general pattern, and maybe one of many such patterns. I hadn't noticed one so simple before.
$endgroup$
– Michael Hardy
May 23 '12 at 17:31
$begingroup$
I suspect it is. I'm just going to conjecture that this will work for all primes 77 mod 100. I'll think about it more when I'm less busy.
$endgroup$
– Eugene
May 23 '12 at 17:36
5
$begingroup$
Are you suggesting that $100000000000003177$ is obviously prime?
$endgroup$
– Robert Israel
May 23 '12 at 17:46
$begingroup$
Fair enough. If it gets too large I suppose it is a problem.
$endgroup$
– Eugene
May 23 '12 at 17:52
2
$begingroup$
My conjecture was for primes 77 mod 100 though rather than an if and only if statement i.e. if n is a prime 77 mod 100 that is not too big, then we can perform a procedure similar to the ones above.
$endgroup$
– Eugene
May 24 '12 at 5:53
|
show 5 more comments
$begingroup$
We have that $677$ is obviously not divisible by $2, 3$, or $5$. Subtracting $77$ leaves $600$ which is not divisible by $7$ or $11$. Adding $13$ to it leaves $690$ which also reduces it to thinking about the two digit number $69$. Likewise subtracting $17$ from this number leaves $660$, and $66$ is not divisible by $17$, and subtracting $57$ leaves $620$ and $62$ is not divisible by $19$, so we reject $19$. Finally, adding $23$ gives $700$, so we reject that, and there's no occasion to go higher than $23$ since we have that $lfloorsqrt{677}rfloor = 26$ so we need only check up to $23$.
As a bonus let's try $977$ which is prime. We have that $977$ is obviously not divisible by $2, 3$, or $5$. Subtracting $77$ leaves $900$ which is not divisible by $7$ or $11$, which also reduces it to thinking about the two digit number $90$ which is neither divisible by $7$ or $11$. Adding $13$ to it leaves $990$ which also reduces it to thinking about the two digit number $99$. Likewise subtracting $17$ from this number leaves $960$, and $96$ is not divisible by $17$, and subtracting $57$ leaves $920$ and $92$ is not divisible by $19$, so we reject $19$. Adding $23$ gives $1000$, so we reject that. Subtracting $87$ leaves $890$ and $89$ is not divisible by $29$, so we reject $29$. Finally, adding $93$ to $977$ gives us $1070$ and $107$ is not divisible by $31$ so we reject $31$ as well. Since we have that $lfloorsqrt{977}rfloor = 31$, we need only check up to $31$ so we are done.
edited May 14 '17 at 16:25
Michael Hardy
1
answered May 23 '12 at 17:24
EugeneEugene
5,03112362
$endgroup$
$begingroup$
Maybe this is a part of a general pattern, and maybe one of many such patterns. I hadn't noticed one so simple before.
$endgroup$
– Michael Hardy
May 23 '12 at 17:31
$begingroup$
I suspect it is. I'm just going to conjecture that this will work for all primes 77 mod 100. I'll think about it more when I'm less busy.
$endgroup$
– Eugene
May 23 '12 at 17:36
5
$begingroup$
Are you suggesting that $100000000000003177$ is obviously prime?
$endgroup$
– Robert Israel
May 23 '12 at 17:46
$begingroup$
Fair enough. If it gets too large I suppose it is a problem.
$endgroup$
– Eugene
May 23 '12 at 17:52
2
$begingroup$
My conjecture was for primes 77 mod 100 though rather than an if and only if statement i.e. if n is a prime 77 mod 100 that is not too big, then we can perform a procedure similar to the ones above.
$endgroup$
– Eugene
May 24 '12 at 5:53
|
show 5 more comments
$begingroup$
We have that $677$ is obviously not divisible by $2, 3$, or $5$. Subtracting $77$ leaves $600$ which is not divisible by $7$ or $11$. Adding $13$ to it leaves $690$ which also reduces it to thinking about the two digit number $69$. Likewise subtracting $17$ from this number leaves $660$, and $66$ is not divisible by $17$, and subtracting $57$ leaves $620$ and $62$ is not divisible by $19$, so we reject $19$. Finally, adding $23$ gives $700$, so we reject that, and there's no occasion to go higher than $23$ since we have that $lfloorsqrt{677}rfloor = 26$ so we need only check up to $23$.
As a bonus let's try $977$ which is prime. We have that $977$ is obviously not divisible by $2, 3$, or $5$. Subtracting $77$ leaves $900$ which is not divisible by $7$ or $11$, which also reduces it to thinking about the two digit number $90$ which is neither divisible by $7$ or $11$. Adding $13$ to it leaves $990$ which also reduces it to thinking about the two digit number $99$. Likewise subtracting $17$ from this number leaves $960$, and $96$ is not divisible by $17$, and subtracting $57$ leaves $920$ and $92$ is not divisible by $19$, so we reject $19$. Adding $23$ gives $1000$, so we reject that. Subtracting $87$ leaves $890$ and $89$ is not divisible by $29$, so we reject $29$. Finally, adding $93$ to $977$ gives us $1070$ and $107$ is not divisible by $31$ so we reject $31$ as well. Since we have that $lfloorsqrt{977}rfloor = 31$, we need only check up to $31$ so we are done.
edited May 14 '17 at 16:25
Michael Hardy
1
answered May 23 '12 at 17:24
EugeneEugene
5,03112362
$endgroup$
We have that $677$ is obviously not divisible by $2, 3$, or $5$. Subtracting $77$ leaves $600$ which is not divisible by $7$ or $11$. Adding $13$ to it leaves $690$ which also reduces it to thinking about the two digit number $69$. Likewise subtracting $17$ from this number leaves $660$, and $66$ is not divisible by $17$, and subtracting $57$ leaves $620$ and $62$ is not divisible by $19$, so we reject $19$. Finally, adding $23$ gives $700$, so we reject that, and there's no occasion to go higher than $23$ since we have that $lfloorsqrt{677}rfloor = 26$ so we need only check up to $23$.
As a bonus let's try $977$ which is prime. We have that $977$ is obviously not divisible by $2, 3$, or $5$. Subtracting $77$ leaves $900$ which is not divisible by $7$ or $11$, which also reduces it to thinking about the two digit number $90$ which is neither divisible by $7$ or $11$. Adding $13$ to it leaves $990$ which also reduces it to thinking about the two digit number $99$. Likewise subtracting $17$ from this number leaves $960$, and $96$ is not divisible by $17$, and subtracting $57$ leaves $920$ and $92$ is not divisible by $19$, so we reject $19$. Adding $23$ gives $1000$, so we reject that. Subtracting $87$ leaves $890$ and $89$ is not divisible by $29$, so we reject $29$. Finally, adding $93$ to $977$ gives us $1070$ and $107$ is not divisible by $31$ so we reject $31$ as well. Since we have that $lfloorsqrt{977}rfloor = 31$, we need only check up to $31$ so we are done.
edited May 14 '17 at 16:25
Michael Hardy
1
answered May 23 '12 at 17:24
EugeneEugene
5,03112362
edited May 14 '17 at 16:25
Michael Hardy
1
edited May 14 '17 at 16:25
Michael Hardy
1
edited May 14 '17 at 16:25
Michael Hardy
1
1
answered May 23 '12 at 17:24
EugeneEugene
5,03112362
answered May 23 '12 at 17:24
EugeneEugene
5,03112362
answered May 23 '12 at 17:24
EugeneEugene
5,03112362
5,03112362
$begingroup$
Maybe this is a part of a general pattern, and maybe one of many such patterns. I hadn't noticed one so simple before.
$endgroup$
– Michael Hardy
May 23 '12 at 17:31
$begingroup$
I suspect it is. I'm just going to conjecture that this will work for all primes 77 mod 100. I'll think about it more when I'm less busy.
$endgroup$
– Eugene
May 23 '12 at 17:36
5
$begingroup$
Are you suggesting that $100000000000003177$ is obviously prime?
$endgroup$
– Robert Israel
May 23 '12 at 17:46
$begingroup$
Fair enough. If it gets too large I suppose it is a problem.
$endgroup$
– Eugene
May 23 '12 at 17:52
2
$begingroup$
My conjecture was for primes 77 mod 100 though rather than an if and only if statement i.e. if n is a prime 77 mod 100 that is not too big, then we can perform a procedure similar to the ones above.
$endgroup$
– Eugene
May 24 '12 at 5:53
|
show 5 more comments
$begingroup$
Maybe this is a part of a general pattern, and maybe one of many such patterns. I hadn't noticed one so simple before.
$endgroup$
– Michael Hardy
May 23 '12 at 17:31
$begingroup$
I suspect it is. I'm just going to conjecture that this will work for all primes 77 mod 100. I'll think about it more when I'm less busy.
$endgroup$
– Eugene
May 23 '12 at 17:36
5
$begingroup$
Are you suggesting that $100000000000003177$ is obviously prime?
$endgroup$
– Robert Israel
May 23 '12 at 17:46
$begingroup$
Fair enough. If it gets too large I suppose it is a problem.
$endgroup$
– Eugene
May 23 '12 at 17:52
2
$begingroup$
My conjecture was for primes 77 mod 100 though rather than an if and only if statement i.e. if n is a prime 77 mod 100 that is not too big, then we can perform a procedure similar to the ones above.
$endgroup$
– Eugene
May 24 '12 at 5:53
$begingroup$
Maybe this is a part of a general pattern, and maybe one of many such patterns. I hadn't noticed one so simple before.
$endgroup$
– Michael Hardy
May 23 '12 at 17:31
$begingroup$
Maybe this is a part of a general pattern, and maybe one of many such patterns. I hadn't noticed one so simple before.
$endgroup$
– Michael Hardy
May 23 '12 at 17:31
$begingroup$
I suspect it is. I'm just going to conjecture that this will work for all primes 77 mod 100. I'll think about it more when I'm less busy.
$endgroup$
– Eugene
May 23 '12 at 17:36
$begingroup$
I suspect it is. I'm just going to conjecture that this will work for all primes 77 mod 100. I'll think about it more when I'm less busy.
$endgroup$
– Eugene
May 23 '12 at 17:36
5
5
$begingroup$
Are you suggesting that $100000000000003177$ is obviously prime?
$endgroup$
– Robert Israel
May 23 '12 at 17:46
$begingroup$
Are you suggesting that $100000000000003177$ is obviously prime?
$endgroup$
– Robert Israel
May 23 '12 at 17:46
$begingroup$
Fair enough. If it gets too large I suppose it is a problem.
$endgroup$
– Eugene
May 23 '12 at 17:52
$begingroup$
Fair enough. If it gets too large I suppose it is a problem.
$endgroup$
– Eugene
May 23 '12 at 17:52
2
2
$begingroup$
My conjecture was for primes 77 mod 100 though rather than an if and only if statement i.e. if n is a prime 77 mod 100 that is not too big, then we can perform a procedure similar to the ones above.
$endgroup$
– Eugene
May 24 '12 at 5:53
$begingroup$
My conjecture was for primes 77 mod 100 though rather than an if and only if statement i.e. if n is a prime 77 mod 100 that is not too big, then we can perform a procedure similar to the ones above.
$endgroup$
– Eugene
May 24 '12 at 5:53
|
show 5 more comments
$begingroup$
This quicker primality test can be done for numbers in any arithmetic progression. For example, rather than $577$ let's consider more generally numbers of the form $rm:m = 10:!n !-! 3.:$ Because we are considering only $1/10$ of the integers, we can effectively reduce an Eratosthenes sieve primality test on $rm:m:$ to a sieve on an integer roughly $1/10,$'th the size of $rm:m,:$ namely $rm:n.:$ Indeed, we have
Theorem $ $ If the positive integer $rm m: =: 10:!n!-!3 < 841 = 29^2:$ then
$$rm 10:!n!-!3 is primeiff 3nmid n, : 7nmid n!-!1, : 11nmid n!+!3,: 13nmid n!+!1,: 17nmid n!-!2,: 19nmid n!-!6,: 23nmid n!+!2 $$
Proof $ $ Since $rm:m < 29^2,:$ if it is composite it must be divisible by a prime $rm:p < 29,:$ hence $rm:p le 23.:$ Consider, e.g. $rm:p = 13:|:10:!n!-!3iff 13:|:10:!n!-!3!+!13 = 10(n!+!1)iff 13:|:n!+!1,:$ etc. $ $ QED
Your example $rm:577 = 10cdot 58 - 3:$ so the above primality test amounts to checking if any of the above $7$ primes divide $rm: 58pm k,:$ for $rm:kle 6,:$ which can be done very quickly mentally, as you did.
answered May 23 '12 at 21:07
Bill DubuqueBill Dubuque
213k29195654
$endgroup$
add a comment |
$begingroup$
This quicker primality test can be done for numbers in any arithmetic progression. For example, rather than $577$ let's consider more generally numbers of the form $rm:m = 10:!n !-! 3.:$ Because we are considering only $1/10$ of the integers, we can effectively reduce an Eratosthenes sieve primality test on $rm:m:$ to a sieve on an integer roughly $1/10,$'th the size of $rm:m,:$ namely $rm:n.:$ Indeed, we have
Theorem $ $ If the positive integer $rm m: =: 10:!n!-!3 < 841 = 29^2:$ then
$$rm 10:!n!-!3 is primeiff 3nmid n, : 7nmid n!-!1, : 11nmid n!+!3,: 13nmid n!+!1,: 17nmid n!-!2,: 19nmid n!-!6,: 23nmid n!+!2 $$
Proof $ $ Since $rm:m < 29^2,:$ if it is composite it must be divisible by a prime $rm:p < 29,:$ hence $rm:p le 23.:$ Consider, e.g. $rm:p = 13:|:10:!n!-!3iff 13:|:10:!n!-!3!+!13 = 10(n!+!1)iff 13:|:n!+!1,:$ etc. $ $ QED
Your example $rm:577 = 10cdot 58 - 3:$ so the above primality test amounts to checking if any of the above $7$ primes divide $rm: 58pm k,:$ for $rm:kle 6,:$ which can be done very quickly mentally, as you did.
answered May 23 '12 at 21:07
Bill DubuqueBill Dubuque
213k29195654
$endgroup$
add a comment |
$begingroup$
This quicker primality test can be done for numbers in any arithmetic progression. For example, rather than $577$ let's consider more generally numbers of the form $rm:m = 10:!n !-! 3.:$ Because we are considering only $1/10$ of the integers, we can effectively reduce an Eratosthenes sieve primality test on $rm:m:$ to a sieve on an integer roughly $1/10,$'th the size of $rm:m,:$ namely $rm:n.:$ Indeed, we have
Theorem $ $ If the positive integer $rm m: =: 10:!n!-!3 < 841 = 29^2:$ then
$$rm 10:!n!-!3 is primeiff 3nmid n, : 7nmid n!-!1, : 11nmid n!+!3,: 13nmid n!+!1,: 17nmid n!-!2,: 19nmid n!-!6,: 23nmid n!+!2 $$
Proof $ $ Since $rm:m < 29^2,:$ if it is composite it must be divisible by a prime $rm:p < 29,:$ hence $rm:p le 23.:$ Consider, e.g. $rm:p = 13:|:10:!n!-!3iff 13:|:10:!n!-!3!+!13 = 10(n!+!1)iff 13:|:n!+!1,:$ etc. $ $ QED
Your example $rm:577 = 10cdot 58 - 3:$ so the above primality test amounts to checking if any of the above $7$ primes divide $rm: 58pm k,:$ for $rm:kle 6,:$ which can be done very quickly mentally, as you did.
answered May 23 '12 at 21:07
Bill DubuqueBill Dubuque
213k29195654
$endgroup$
This quicker primality test can be done for numbers in any arithmetic progression. For example, rather than $577$ let's consider more generally numbers of the form $rm:m = 10:!n !-! 3.:$ Because we are considering only $1/10$ of the integers, we can effectively reduce an Eratosthenes sieve primality test on $rm:m:$ to a sieve on an integer roughly $1/10,$'th the size of $rm:m,:$ namely $rm:n.:$ Indeed, we have
Theorem $ $ If the positive integer $rm m: =: 10:!n!-!3 < 841 = 29^2:$ then
$$rm 10:!n!-!3 is primeiff 3nmid n, : 7nmid n!-!1, : 11nmid n!+!3,: 13nmid n!+!1,: 17nmid n!-!2,: 19nmid n!-!6,: 23nmid n!+!2 $$
Proof $ $ Since $rm:m < 29^2,:$ if it is composite it must be divisible by a prime $rm:p < 29,:$ hence $rm:p le 23.:$ Consider, e.g. $rm:p = 13:|:10:!n!-!3iff 13:|:10:!n!-!3!+!13 = 10(n!+!1)iff 13:|:n!+!1,:$ etc. $ $ QED
Your example $rm:577 = 10cdot 58 - 3:$ so the above primality test amounts to checking if any of the above $7$ primes divide $rm: 58pm k,:$ for $rm:kle 6,:$ which can be done very quickly mentally, as you did.
answered May 23 '12 at 21:07
Bill DubuqueBill Dubuque
213k29195654
edited May 23 '12 at 21:19
user242
answered May 23 '12 at 21:07
Bill DubuqueBill Dubuque
213k29195654
answered May 23 '12 at 21:07
Bill DubuqueBill Dubuque
213k29195654
answered May 23 '12 at 21:07
Bill DubuqueBill Dubuque
213k29195654
213k29195654
add a comment |
add a comment |
$begingroup$
There is a very nice paper about this, Guy, Lacampagne, and Selfridge, Primes at a glance, Mathematics of Computation Vol. 48, No. 177, Jan., 1987, pages 183 to 202. I think that back issues of this journal are freely available at the American Mathematical Society website.
There is a follow-up paper by Agoh, Erdos, and Granville, Primes at a (somewhat lengthy) glance, The American Mathematical Monthly Vol. 104, No. 10, Dec., 1997, pages 943 to 945, but I'm pretty sure that one's behind a paywall if you don't connect from a subscriber.
EDIT: Link to Primes at a glance mentioned above.
edited Nov 22 '14 at 9:50
Daniel R
2,49532035
answered May 24 '12 at 1:37
Gerry MyersonGerry Myerson
147k8151304
$endgroup$
add a comment |
$begingroup$
There is a very nice paper about this, Guy, Lacampagne, and Selfridge, Primes at a glance, Mathematics of Computation Vol. 48, No. 177, Jan., 1987, pages 183 to 202. I think that back issues of this journal are freely available at the American Mathematical Society website.
There is a follow-up paper by Agoh, Erdos, and Granville, Primes at a (somewhat lengthy) glance, The American Mathematical Monthly Vol. 104, No. 10, Dec., 1997, pages 943 to 945, but I'm pretty sure that one's behind a paywall if you don't connect from a subscriber.
EDIT: Link to Primes at a glance mentioned above.
edited Nov 22 '14 at 9:50
Daniel R
2,49532035
answered May 24 '12 at 1:37
Gerry MyersonGerry Myerson
147k8151304
$endgroup$
add a comment |
$begingroup$
There is a very nice paper about this, Guy, Lacampagne, and Selfridge, Primes at a glance, Mathematics of Computation Vol. 48, No. 177, Jan., 1987, pages 183 to 202. I think that back issues of this journal are freely available at the American Mathematical Society website.
There is a follow-up paper by Agoh, Erdos, and Granville, Primes at a (somewhat lengthy) glance, The American Mathematical Monthly Vol. 104, No. 10, Dec., 1997, pages 943 to 945, but I'm pretty sure that one's behind a paywall if you don't connect from a subscriber.
EDIT: Link to Primes at a glance mentioned above.
edited Nov 22 '14 at 9:50
Daniel R
2,49532035
answered May 24 '12 at 1:37
Gerry MyersonGerry Myerson
147k8151304
$endgroup$
There is a very nice paper about this, Guy, Lacampagne, and Selfridge, Primes at a glance, Mathematics of Computation Vol. 48, No. 177, Jan., 1987, pages 183 to 202. I think that back issues of this journal are freely available at the American Mathematical Society website.
There is a follow-up paper by Agoh, Erdos, and Granville, Primes at a (somewhat lengthy) glance, The American Mathematical Monthly Vol. 104, No. 10, Dec., 1997, pages 943 to 945, but I'm pretty sure that one's behind a paywall if you don't connect from a subscriber.
EDIT: Link to Primes at a glance mentioned above.
edited Nov 22 '14 at 9:50
Daniel R
2,49532035
answered May 24 '12 at 1:37
Gerry MyersonGerry Myerson
147k8151304
edited Nov 22 '14 at 9:50
Daniel R
2,49532035
edited Nov 22 '14 at 9:50
Daniel R
2,49532035
edited Nov 22 '14 at 9:50
Daniel R
2,49532035
2,49532035
answered May 24 '12 at 1:37
Gerry MyersonGerry Myerson
147k8151304
answered May 24 '12 at 1:37
Gerry MyersonGerry Myerson
147k8151304
answered May 24 '12 at 1:37
Gerry MyersonGerry Myerson
147k8151304
147k8151304
add a comment |
add a comment |
$begingroup$
can't resist following the pattern: 877. Additionally, need to test for 29 (but trivial)
answered May 23 '12 at 17:53
karakfakarakfa
2,025811
$endgroup$
2
$begingroup$
$29 mid 87$, so that reduces to two digits.
$endgroup$
– Michael Hardy
May 23 '12 at 20:47
1
$begingroup$
or subtracting 87 from 877 you'll get 790 which is not divisible by 29.
$endgroup$
– Keivan
May 23 '12 at 23:59
add a comment |
$begingroup$
can't resist following the pattern: 877. Additionally, need to test for 29 (but trivial)
answered May 23 '12 at 17:53
karakfakarakfa
2,025811
$endgroup$
2
$begingroup$
$29 mid 87$, so that reduces to two digits.
$endgroup$
– Michael Hardy
May 23 '12 at 20:47
1
$begingroup$
or subtracting 87 from 877 you'll get 790 which is not divisible by 29.
$endgroup$
– Keivan
May 23 '12 at 23:59
add a comment |
$begingroup$
can't resist following the pattern: 877. Additionally, need to test for 29 (but trivial)
answered May 23 '12 at 17:53
karakfakarakfa
2,025811
$endgroup$
can't resist following the pattern: 877. Additionally, need to test for 29 (but trivial)
answered May 23 '12 at 17:53
karakfakarakfa
2,025811
answered May 23 '12 at 17:53
karakfakarakfa
2,025811
answered May 23 '12 at 17:53
karakfakarakfa
2,025811
answered May 23 '12 at 17:53
karakfakarakfa
2,025811
2,025811
2
$begingroup$
$29 mid 87$, so that reduces to two digits.
$endgroup$
– Michael Hardy
May 23 '12 at 20:47
1
$begingroup$
or subtracting 87 from 877 you'll get 790 which is not divisible by 29.
$endgroup$
– Keivan
May 23 '12 at 23:59
add a comment |
2
$begingroup$
$29 mid 87$, so that reduces to two digits.
$endgroup$
– Michael Hardy
May 23 '12 at 20:47
1
$begingroup$
or subtracting 87 from 877 you'll get 790 which is not divisible by 29.
$endgroup$
– Keivan
May 23 '12 at 23:59
2
2
$begingroup$
$29 mid 87$, so that reduces to two digits.
$endgroup$
– Michael Hardy
May 23 '12 at 20:47
$begingroup$
$29 mid 87$, so that reduces to two digits.
$endgroup$
– Michael Hardy
May 23 '12 at 20:47
1
1
$begingroup$
or subtracting 87 from 877 you'll get 790 which is not divisible by 29.
$endgroup$
– Keivan
May 23 '12 at 23:59
$begingroup$
or subtracting 87 from 877 you'll get 790 which is not divisible by 29.
$endgroup$
– Keivan
May 23 '12 at 23:59
add a comment |
$begingroup$
How quick is quick enough?
$n=1601$. Let $x=39$. $1601=40^2+1=40x+41=x^2+x+41$ which, as is well known, is prime for integer $0leqslant x<40$.
$n=2081$ obviously has the form $x^2+5y^2$ ($x=9, y=20$) so every prime factor of $n$ has an even tens-digit. Clearly not 3.
- 7: $2100-n=19$ and $7nmid 19$.
- 23: $2300-n=219$; $230-219=11$ and $23nmid 11$.
- 29: $n+29=2110$; $211+29=240$ and $29nmid 24$.
- 41: $n-41=2040$; $5cdot 41=205$ so $41nmid 204$.
- 43: $43^2$ ends in 9; $43cdot 47=45^2-2^2=2021ne n$ and any other composite with smallest prime factor $geqslant 43$ would be $>n$.
answered Jan 27 at 18:17
Rosie FRosie F
1,379416
$endgroup$
add a comment |
$begingroup$
How quick is quick enough?
$n=1601$. Let $x=39$. $1601=40^2+1=40x+41=x^2+x+41$ which, as is well known, is prime for integer $0leqslant x<40$.
$n=2081$ obviously has the form $x^2+5y^2$ ($x=9, y=20$) so every prime factor of $n$ has an even tens-digit. Clearly not 3.
- 7: $2100-n=19$ and $7nmid 19$.
- 23: $2300-n=219$; $230-219=11$ and $23nmid 11$.
- 29: $n+29=2110$; $211+29=240$ and $29nmid 24$.
- 41: $n-41=2040$; $5cdot 41=205$ so $41nmid 204$.
- 43: $43^2$ ends in 9; $43cdot 47=45^2-2^2=2021ne n$ and any other composite with smallest prime factor $geqslant 43$ would be $>n$.
answered Jan 27 at 18:17
Rosie FRosie F
1,379416
$endgroup$
add a comment |
$begingroup$
How quick is quick enough?
$n=1601$. Let $x=39$. $1601=40^2+1=40x+41=x^2+x+41$ which, as is well known, is prime for integer $0leqslant x<40$.
$n=2081$ obviously has the form $x^2+5y^2$ ($x=9, y=20$) so every prime factor of $n$ has an even tens-digit. Clearly not 3.
- 7: $2100-n=19$ and $7nmid 19$.
- 23: $2300-n=219$; $230-219=11$ and $23nmid 11$.
- 29: $n+29=2110$; $211+29=240$ and $29nmid 24$.
- 41: $n-41=2040$; $5cdot 41=205$ so $41nmid 204$.
- 43: $43^2$ ends in 9; $43cdot 47=45^2-2^2=2021ne n$ and any other composite with smallest prime factor $geqslant 43$ would be $>n$.
answered Jan 27 at 18:17
Rosie FRosie F
1,379416
$endgroup$
How quick is quick enough?
$n=1601$. Let $x=39$. $1601=40^2+1=40x+41=x^2+x+41$ which, as is well known, is prime for integer $0leqslant x<40$.
$n=2081$ obviously has the form $x^2+5y^2$ ($x=9, y=20$) so every prime factor of $n$ has an even tens-digit. Clearly not 3.
- 7: $2100-n=19$ and $7nmid 19$.
- 23: $2300-n=219$; $230-219=11$ and $23nmid 11$.
- 29: $n+29=2110$; $211+29=240$ and $29nmid 24$.
- 41: $n-41=2040$; $5cdot 41=205$ so $41nmid 204$.
- 43: $43^2$ ends in 9; $43cdot 47=45^2-2^2=2021ne n$ and any other composite with smallest prime factor $geqslant 43$ would be $>n$.
answered Jan 27 at 18:17
Rosie FRosie F
1,379416
answered Jan 27 at 18:17
Rosie FRosie F
1,379416
answered Jan 27 at 18:17
Rosie FRosie F
1,379416
answered Jan 27 at 18:17
Rosie FRosie F
1,379416
1,379416
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%2f148852%2fa-big-number-that-is-obviously-prime%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$
When I read the title first thing that came to my mind was primality certificate. It would be more obvious to me if the number was given with a certificate. Anyway, great question ;-)
$endgroup$
– dtldarek
May 23 '12 at 21:48
$begingroup$
I believe that $lfloorsqrt{577}rfloor = 24$...
$endgroup$
– u8y7541
May 13 '17 at 21:51
$begingroup$
@u8y7541 : Fixed. $23$ is not the "floor" of $sqrt{577}$ but it is the "prime floor" of $sqrt{577}. qquad$
$endgroup$
– Michael Hardy
May 14 '17 at 16:19