For those who enjoy burning cpu cycles !
m1277 = 2 ^ 1277 - 1 is not prime.
It easy to check it with the Lucas-Lehmer test.
But we don't know any of its divisors, which is quite fascinating.
My favourite prime checking algorithm is that for n < 100 if it looks prime, it is prime.
freehorse 12 hours ago [-]
Up to 100 it is relatively simple, if you remove the even numbers, the multiples of 3 (summing up their digits recursively gives 3 6 or 9), and those that end at 5, you end up with 25 numbers out of which 22 (88%) are primes. If you further exclude 49 which you should remember is 7^2 from the multiplication table, and 77 that is obviously divisible by 7, you are left with 22/23 chance a number that passes these exclusion criteria is not 91 and hence it is a prime.
jeffbee 11 hours ago [-]
> summing up their digits recursively gives 3 6 or 9
What does this part mean? For example 57.
zdimension 11 hours ago [-]
57 is 3 times 19.
The standard divisibility rule for 3, 6 and 9 in base 10 is to sum the digits until you only have one left and check if it's one of those. Here, 5+7=12, 1+2=3, so 57 is divisible by 3.
squigz 1 hours ago [-]
Math is not my strong suit at all, so I probably won't grok this, but that kind of blows my mind, so I'm curious... how?! That works for any arbitrarily large number?
Math is crazy!... still don't want to study it though!
When checking whether it is a multiple of some k, you can add/subtract multiples of k without changing the result, and those 99...9 are multiples of both 3 and 9.
is. Apply the same rule as often as you want -- that is, until you only have one digit left, because then it won't get simpler anymore.
jeffbee 11 hours ago [-]
Ah I see what is meant by recursively here. Thanks!
hollerith 11 hours ago [-]
5 plus 7 is 12, which of course has a 1 and a 2, the sum of which is 3.
throwaway81523 13 hours ago [-]
Like the famous Grothendieck prime of course.
xorbax 13 hours ago [-]
Definitely makes me feel better about my own work
floydian10 2 hours ago [-]
91 should be prime, ridiculous that it isn't
emaccumber 13 hours ago [-]
The annoying child in me will always remember correcting my freshman math teacher when he needed a prime number and wrote 91 on the chalkboard.
GMoromisato 13 hours ago [-]
Are there any numbers that don't look prime but are, in fact, prime? [Other than 2, I suppose.]
andruby 13 hours ago [-]
11, 13, 17 and 19 used to trip me up. And maybe 67
mootothemax 9 hours ago [-]
67 has absolutely no right to be prime. Sitting there looking all innocent.
ridiculous_fish 12 hours ago [-]
Except 91.
conradev 12 hours ago [-]
This only works if you know multiplication tables which is not a given in America these days.
gosub100 11 hours ago [-]
"not given" != "not able to learn"
13 hours ago [-]
wbl 7 hours ago [-]
57
NetMageSCW 12 hours ago [-]
Pay wall.
WolfeReader 12 hours ago [-]
Imagine browsing the web without an ad blocker.
Nevermark 14 hours ago [-]
Just grab some paper, a pen, and check that no number equal or smaller than its square root divides into it evenly.
That is it. That is all. Pish posh.
WCSTombs 14 hours ago [-]
The example given in the article is 2^127 - 1, which was historically proved to be prime without computers using a clever method now known as the Lucas-Lehmer test. Your algorithm is not practical for that number.
Nevermark 13 hours ago [-]
Ah, but I can assure you, it is just that simple.
If a number is not prime, then it is the product of at least two numbers smaller than itself.
If any of them are larger than its square root, all others must be smaller, or their product would be larger than the candidate prime.
Ergo, just check that the candidate is not evenly divisible by any number equal or lower than its square root.
This reasoning holds, independent of scale.
QED. Check mate. Shazam.
mysterydip 13 hours ago [-]
Perfect example of how "if the code is compact, it's fast" can be deceiving :)
Nevermark 8 hours ago [-]
Search is all you need!
If you have the time.
Or if we can expand quantum superposition algorithms from 2^N states, for quantum circuits with N control qubits, to 2^(T*N) superpositions over T time steps, via some kind of superposition tree recursion. The number of superpositions increasing exponentially for T steps (and then reducing for another T steps) on a single recursive physical circuit.
That is not supported by the physical laws we have, but it is an interesting idea.
xpe 11 hours ago [-]
The obvious and naive method described above is O(sqrt(N)). For N ~= 2 ^ 127, that is about 2 ^ 64. / The Lucas-Lehmer method described in the article is better (how much better is an exercise for the reader).
gsliepen 5 hours ago [-]
You are assuming division itself is an O(1) operation. However, it also scales with the size of the number. So more correct would be to say that this naive method is O(sqrt(N) log(N) log(log(N))).
great_wubwub 14 hours ago [-]
/r/whoosh
eps 13 hours ago [-]
Nah, the joke just was fairly flat and low-effort.
tmtvl 3 hours ago [-]
Even better: you only have to check primes smaller than or equal to the square root.
politelemon 14 hours ago [-]
[flagged]
zamadatix 14 hours ago [-]
The scourge of HN submission rules - "you can submit anything and it's up to everyone else to actually be able to access it".
The HN rule is that anything can be posted if it is accessible to everyone, including via a paywall workaround if it has a paywall that is porous.
The community has converged on this being the least-worst approach after wrestling with the issue for well over a decade, and it's sufficient to helpfully post the archive link without a snarky editorial comment :)
Terr_ 14 hours ago [-]
If I had my 'druthers designing a new link-share/comment system, the visibility (and mirrors or excerpts) for the target would be part of the model.
In other words, an icon showing whatever-wall status, submitter can add an alternate link, etc.
smcin 11 hours ago [-]
The standard etiquette on HN is not to bother saying that, just post its archive link already.
xeonmc 14 hours ago [-]
I guess that's the answer then -- you need a subscription instead of a computer.
NSPG911 13 hours ago [-]
i found out that most articles behind paywalls dont even need the wayback machine to be viewed
if you are using firefox, just enter reading mode and you can read the entire article without popups in your preferred background, text color, font, etc
Rendered at 11:51:02 GMT+0000 (UTC) with Wasmer Edge.
http://calcoastrails.com/
(factorial(170,141,183,460,469,231,731,687,303,715,884,105,726) + 1)%(170,141,183,460,469,231,731,687,303,715,884,105,727) == 0
What does this part mean? For example 57.
The standard divisibility rule for 3, 6 and 9 in base 10 is to sum the digits until you only have one left and check if it's one of those. Here, 5+7=12, 1+2=3, so 57 is divisible by 3.
Math is crazy!... still don't want to study it though!
123456 = 1 * 100000 + 2 * 10000 + 3 * 1000 + 4 * 100 + 5 * 10 + 6 = 1 * (99999+1) + 2 * (9999+1) + 3 * (999+1) + 4 * (99+1) + 5 * (9+1) + 6
When checking whether it is a multiple of some k, you can add/subtract multiples of k without changing the result, and those 99...9 are multiples of both 3 and 9.
So 123456 is a multiple of 3 (or 9) iff
1 * 1 + 2 * 1 + 3 * 1 + 4 * 1 + 5 * 1 + 6 * 1 = 1 + 2 + 3 + 4 + 5 + 6
is. Apply the same rule as often as you want -- that is, until you only have one digit left, because then it won't get simpler anymore.
That is it. That is all. Pish posh.
If a number is not prime, then it is the product of at least two numbers smaller than itself.
If any of them are larger than its square root, all others must be smaller, or their product would be larger than the candidate prime.
Ergo, just check that the candidate is not evenly divisible by any number equal or lower than its square root.
This reasoning holds, independent of scale.
QED. Check mate. Shazam.
If you have the time.
Or if we can expand quantum superposition algorithms from 2^N states, for quantum circuits with N control qubits, to 2^(T*N) superpositions over T time steps, via some kind of superposition tree recursion. The number of superpositions increasing exponentially for T steps (and then reducing for another T steps) on a single recursive physical circuit.
That is not supported by the physical laws we have, but it is an interesting idea.
https://archive.is/8R0Fq
The community has converged on this being the least-worst approach after wrestling with the issue for well over a decade, and it's sufficient to helpfully post the archive link without a snarky editorial comment :)
In other words, an icon showing whatever-wall status, submitter can add an alternate link, etc.
if you are using firefox, just enter reading mode and you can read the entire article without popups in your preferred background, text color, font, etc