The Lucas-Lehmer Prime Number Test(scientificamerican.com)
scientificamerican.com
The Lucas-Lehmer Prime Number Test
https://www.scientificamerican.com/article/how-to-identify-a-prime-number-without-a-computer/
https://archive.md/8R0Fq
57 comments
The original Agrawal, Kayal, Saxena "Primes is in P" paper is actually an amazing effort in clarity https://annals.math.princeton.edu/wp-content/uploads/annals-... .
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.
The Lehmers are cool people…
Ron’s got a train spotting site.
http://calcoastrails.com/
http://calcoastrails.com/
I knew about this site and knew about the Lucas-Lehmer test, but I never would have made the connection between the two. People are kind of amazing.
I knew Derrick Lehmer Jr before he passed away, just happened to know the name.
That's easy.
(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
(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
My favourite prime checking algorithm is that for n < 100 if it looks prime, it is prime.
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.
> (summing up their digits recursively gives 3 6 or 9)
My fun fact is that this type of operation (repeatedly applying a child operation until you reach a fixed point) is called persistence.
https://en.wikipedia.org/wiki/Persistence_of_a_number
The fixed point here being that if you add up a list of 1 digits, you'll always reach the same number (`sum([1]) = 1`). The best known is probably the hailstone sequence.
https://en.wikipedia.org/wiki/Collatz_conjecture
I'm partial to multiplicative persistence.
https://www.youtube.com/watch?v=Wim9WJeDTHQ [15m]
My fun fact is that this type of operation (repeatedly applying a child operation until you reach a fixed point) is called persistence.
https://en.wikipedia.org/wiki/Persistence_of_a_number
The fixed point here being that if you add up a list of 1 digits, you'll always reach the same number (`sum([1]) = 1`). The best known is probably the hailstone sequence.
https://en.wikipedia.org/wiki/Collatz_conjecture
I'm partial to multiplicative persistence.
https://www.youtube.com/watch?v=Wim9WJeDTHQ [15m]
> summing up their digits recursively gives 3 6 or 9
What does this part mean? For example 57.
What does this part mean? For example 57.
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.
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 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!
Math is crazy!... still don't want to study it though!
Yes. A number like
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.
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.
It is basically because $10 mod 3 == 1$ (as 10 = 3*3 + 1). So if you are in the ring modulo 3, where every number is equal to the remainder of its division by 3, the sum of the digits of the number in its decimal representation equals the number itself (modulo 3), because in that ring 10 is actually 1, so the 10s in the decimal sum become 1s. Ie if n_k is the kth digit of n, you have
Of course, summing up the digits may not give you a 1-digit number, but it gives you a number that you know is divisible by 3 (if the original number is divisible by 3). So you can apply the same idea/process again, summing up the digits of that number, and get another number that is divisible by 3. Repeat until you end up with one digit (hence the recursion mentioned).
(mod 3) n == n_0 + n_1*10 + n_2*10^2 + ... == n_0 + n_1 + n_2 + ...
Of course, summing up the digits may not give you a 1-digit number, but it gives you a number that you know is divisible by 3 (if the original number is divisible by 3). So you can apply the same idea/process again, summing up the digits of that number, and get another number that is divisible by 3. Repeat until you end up with one digit (hence the recursion mentioned).
[deleted]
Ah I see what is meant by recursively here. Thanks!
5 plus 7 is 12, which of course has a 1 and a 2, the sum of which is 3.
Like the famous Grothendieck prime of course.
Definitely makes me feel better about my own work
91 should be prime, ridiculous that it isn't
Agree. Plus now I now need to release a security patch for the hand-rolled crypto library I built.
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.
I wonder what the underlying human intuition is for 'prime-ness' and why it might break down with larger numbers. Odd numbers in the rightmost position? The 'shape' of the number (phonaesthesia, the bouba/kiki effect)? Maybe they just sort of feel scary?
For n < 100 to be composite you need a factor < sqrt(100) = 10. Rules for 2, 3, 5 are easy to try quickly. That leaves 7, but up to 7*9 you should remember it from multiplication tables. 77 is quite obviously divisible by 11 too, and then it's 7*13 = 91 as the last boss. But I feel that once you realize how special 91 is in that context, you won't forget it again.
Are there any numbers that don't look prime but are, in fact, prime? [Other than 2, I suppose.]
11, 13, 17 and 19 used to trip me up. And maybe 67
67 has absolutely no right to be prime. Sitting there looking all innocent.
Maybe that’s the real secret behind the 6-7 meme going around
Except 91.
[deleted]
[deleted]
Except 91
57
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.
That is it. That is all. Pish posh.
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.
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.
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.
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).
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))).
I was both hoping and fearing that someone would correct my simplification. (That is more nested logs than I would’ve guessed however.)
Perfect example of how "if the code is compact, it's fast" can be deceiving :)
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.
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.
[deleted]
Even better: you only have to check primes smaller than or equal to the square root.
politelemon(4)