| ▲ | The Lucas-Lehmer Prime Number Test(scientificamerican.com) |
| 76 points by beardyw 8 days ago | 36 comments |
| https://archive.md/8R0Fq |
|
| ▲ | oliviersca 2 hours ago | parent | next [-] |
| 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. |
|
| ▲ | jmount 11 hours ago | parent | prev | next [-] |
| 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-... . |
|
| ▲ | roflchoppa 3 hours ago | parent | prev | next [-] |
| The Lehmers are cool people…
Ron’s got a train spotting site. http://calcoastrails.com/ |
| |
| ▲ | jrockway 3 hours ago | parent [-] | | 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. |
|
|
| ▲ | 30030 3 hours ago | parent | prev | next [-] |
| 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 |
|
| ▲ | IsTom 13 hours ago | parent | prev | next [-] |
| My favourite prime checking algorithm is that for n < 100 if it looks prime, it is prime. |
| |
| ▲ | freehorse 12 hours ago | parent | next [-] | | 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 | parent [-] | | > summing up their digits recursively gives 3 6 or 9 What does this part mean? For example 57. | | |
| ▲ | zdimension 11 hours ago | parent | next [-] | | 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 an hour ago | parent | next [-] | | 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! | | |
| ▲ | moring 5 minutes ago | parent [-] | | 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. |
| |
| ▲ | jeffbee 11 hours ago | parent | prev [-] | | Ah I see what is meant by recursively here. Thanks! |
| |
| ▲ | hollerith 11 hours ago | parent | prev [-] | | 5 plus 7 is 12, which of course has a 1 and a 2, the sum of which is 3. |
|
| |
| ▲ | throwaway81523 13 hours ago | parent | prev | next [-] | | Like the famous Grothendieck prime of course. | | | |
| ▲ | floydian10 2 hours ago | parent | prev | next [-] | | 91 should be prime, ridiculous that it isn't | |
| ▲ | emaccumber 13 hours ago | parent | prev | next [-] | | 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 | parent | prev | next [-] | | Are there any numbers that don't look prime but are, in fact, prime? [Other than 2, I suppose.] | | | |
| ▲ | ridiculous_fish 12 hours ago | parent | prev | next [-] | | Except 91. | |
| ▲ | conradev 12 hours ago | parent | prev | next [-] | | This only works if you know multiplication tables which is not a given in America these days. | | | |
| ▲ | wbl 7 hours ago | parent | prev [-] | | 57 |
|
|
| ▲ | NetMageSCW 11 hours ago | parent | prev | next [-] |
| Pay wall. |
| |
|
| ▲ | Nevermark 14 hours ago | parent | prev [-] |
| 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 13 hours ago | parent | next [-] | | 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 | parent | next [-] | | 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 12 hours ago | parent | next [-] | | Perfect example of how "if the code is compact, it's fast" can be deceiving :) | | |
| ▲ | Nevermark 8 hours ago | parent [-] | | 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 | parent | prev [-] | | 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 | parent [-] | | 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 13 hours ago | parent | prev [-] | | /r/whoosh | | |
| ▲ | eps 12 hours ago | parent [-] | | Nah, the joke just was fairly flat and low-effort. |
|
| |
| ▲ | tmtvl 3 hours ago | parent | prev [-] | | Even better: you only have to check primes smaller than or equal to the square root. |
|
