5 ms·
The Lucas-Lehmer Prime Number Test
https://archive.md/8R0Fq https://archive.md/8R0Fq
- politelemon 11mo ago[flagged]
- smcin 11mo agoThe standard etiquette on HN is not to bother saying that, just post its archive link already.
- xeonmc 11mo agoI guess that's the answer then -- you need a subscription instead of a computer.
- zamadatix 11mo agoThe scourge of HN submission rules - "you can submit anything and it's up to everyone else to actually be able to access it". https://archive.is/8R0Fq https://archive.is/8R0Fq
- Terr_ 11mo agoIf 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.
- tomhow 11mo agoThe 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 :)
- NSPG911 11mo agoi 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
- Nevermark 11mo agoJust 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 11mo agoThe 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.
- great_wubwub 11mo ago/r/whoosh
- eps 11mo agoNah, the joke just was fairly flat and low-effort.
- Nevermark 11mo agoAh, 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 11mo agoPerfect example of how "if the code is compact, it's fast" can be deceiving :)
- Nevermark 11mo agoSearch 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.
- IsTom 11mo agoMy favourite prime checking algorithm is that for n < 100 if it looks prime, it is prime.
- throwaway81523 11mo agoLike the famous Grothendieck prime of course.
- xorbax 11mo agoDefinitely makes me feel better about my own work
- emaccumber 11mo agoThe annoying child in me will always remember correcting my freshman math teacher when he needed a prime number and wrote 91 on the chalkboard.
- deleted 11mo ago[deleted]
- GMoromisato 11mo agoAre there any numbers that don't look prime but are, in fact, prime? [Other than 2, I suppose.]
- andruby 11mo ago11, 13, 17 and 19 used to trip me up. And maybe 67
- mootothemax 11mo ago67 has absolutely no right to be prime. Sitting there looking all innocent.
- bombcar 11mo ago
- NetMageSCW 11mo agoPay wall.
- WolfeReader 11mo agoImagine browsing the web without an ad blocker.
- jmount 11mo agoThe 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-v160-n2-p12.pdf https://annals.math.princeton.edu/wp-content/uploads/annals-... .
- roflchoppa 11mo agoThe Lehmers are cool people… Ron’s got a train spotting site. http://calcoastrails.com/ http://calcoastrails.com/
- jrockway 11mo agoI 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.
- roflchoppa 11mo agoI knew Derrick Lehmer Jr before he passed away, just happened to know the name.
- 30030 11mo agoThat'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
- oliviersca 11mo agoFor 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.
- John-Tony 11mo ago[dead]