Talk:Lucas-Lehmer test: Difference between revisions
m (→M23,209 is 36 CPU hours ≡ 1979: yeah...) |
|||
(16 intermediate revisions by 9 users not shown) | |||
Line 1: | Line 1: | ||
== |
== M<small><sub>23,209</sub></small> is 36 CPU hours ≡ 1979 == |
||
Welcome to 1979! |
Welcome to 1979! |
||
:Yeah. I know. :-) --[[User:Short Circuit|Short Circuit]] 07:55, 21 February 2008 (MST) |
:Yeah. I know. :-) --[[User:Short Circuit|Short Circuit]] 07:55, 21 February 2008 (MST) |
||
===List of known Mersenne primes=== |
|||
==List of known Mersenne primes== |
|||
The table below lists all known Mersenne primes: |
|||
{| class="wikitable" |
{| class="wikitable" |
||
|- |
|- |
||
Line 15: | Line 16: | ||
| align="right" | 1 |
| align="right" | 1 |
||
| align="right" | 2 |
| align="right" | 2 |
||
| align="right" | |
| align="right" | 3 (number)|3 |
||
| align="right" | 1 |
| align="right" | 1 |
||
| ''ancient'' |
| ''ancient'' |
||
Line 22: | Line 23: | ||
| align="right" | 2 |
| align="right" | 2 |
||
| align="right" | 3 |
| align="right" | 3 |
||
| align="right" | |
| align="right" | 7 (number)|7 |
||
| align="right" | 1 |
| align="right" | 1 |
||
| ''ancient'' |
| ''ancient'' |
||
Line 29: | Line 30: | ||
| align="right" | 3 |
| align="right" | 3 |
||
| align="right" | 5 |
| align="right" | 5 |
||
| align="right" | |
| align="right" | 31 (number)|31 |
||
| align="right" | 2 |
| align="right" | 2 |
||
| ''ancient'' |
| ''ancient'' |
||
Line 36: | Line 37: | ||
| align="right" | 4 |
| align="right" | 4 |
||
| align="right" | 7 |
| align="right" | 7 |
||
| align="right" | |
| align="right" | 127 (number)|127 |
||
| align="right" | 3 |
| align="right" | 3 |
||
| ''ancient'' |
| ''ancient'' |
||
Line 53: | Line 54: | ||
| align="right" | 6 |
| align="right" | 6 |
||
| 1588 |
| 1588 |
||
| |
| Pietro Cataldi|Cataldi |
||
|- |
|- |
||
| align="right" | 7 |
| align="right" | 7 |
||
Line 60: | Line 61: | ||
| align="right" | 6 |
| align="right" | 6 |
||
| 1588 |
| 1588 |
||
| |
| Pietro Cataldi|Cataldi |
||
|- |
|- |
||
| align="right" | 8 |
| align="right" | 8 |
||
Line 67: | Line 68: | ||
| align="right" | 10 |
| align="right" | 10 |
||
| 1772 |
| 1772 |
||
| |
| Leonhard Euler|Euler |
||
|- |
|- |
||
| align="right" | 9 |
| align="right" | 9 |
||
Line 74: | Line 75: | ||
| align="right" | 19 |
| align="right" | 19 |
||
| 1883 |
| 1883 |
||
| |
| Ivan Mikheevich Pervushin|Pervushin |
||
|- |
|- |
||
| align="right" | 10 |
| align="right" | 10 |
||
Line 81: | Line 82: | ||
| align="right" | 27 |
| align="right" | 27 |
||
| 1911 |
| 1911 |
||
| |
| R. E. Powers|Powers |
||
|- |
|- |
||
| align="right" | 11 |
| align="right" | 11 |
||
Line 88: | Line 89: | ||
| align="right" | 33 |
| align="right" | 33 |
||
| 1914 |
| 1914 |
||
| |
| R. E. Powers|Powers[http://primes.utm.edu/notes/fauquem.html] |
||
|- |
|- |
||
| align="right" | 12 |
| align="right" | 12 |
||
Line 95: | Line 96: | ||
| align="right" | 39 |
| align="right" | 39 |
||
| 1876 |
| 1876 |
||
| |
| Edouard Lucas|Lucas |
||
|- |
|- |
||
| align="right" | 13 |
| align="right" | 13 |
||
Line 101: | Line 102: | ||
| align="right" | 686479766…115057151 |
| align="right" | 686479766…115057151 |
||
| align="right" | 157 |
| align="right" | 157 |
||
| |
| January 30 1952 |
||
| |
| Raphael M. Robinson|Robinson |
||
|- |
|- |
||
| align="right" | 14 |
| align="right" | 14 |
||
Line 108: | Line 109: | ||
| align="right" | 531137992…031728127 |
| align="right" | 531137992…031728127 |
||
| align="right" | 183 |
| align="right" | 183 |
||
| |
| January 30 1952 |
||
| |
| Raphael M. Robinson|Robinson |
||
|- |
|- |
||
| align="right" | 15 |
| align="right" | 15 |
||
Line 115: | Line 116: | ||
| align="right" | 104079321…168729087 |
| align="right" | 104079321…168729087 |
||
| align="right" | 386 |
| align="right" | 386 |
||
| |
| June 25 1952 |
||
| |
| Raphael M. Robinson|Robinson |
||
|- |
|- |
||
| align="right" | 16 |
| align="right" | 16 |
||
Line 122: | Line 123: | ||
| align="right" | 147597991…697771007 |
| align="right" | 147597991…697771007 |
||
| align="right" | 664 |
| align="right" | 664 |
||
| |
| October 7 1952 |
||
| |
| Raphael M. Robinson|Robinson |
||
|- |
|- |
||
| align="right" | 17 |
| align="right" | 17 |
||
Line 129: | Line 130: | ||
| align="right" | 446087557…132836351 |
| align="right" | 446087557…132836351 |
||
| align="right" | 687 |
| align="right" | 687 |
||
| |
| October 9 1952 |
||
| |
| Raphael M. Robinson|Robinson |
||
|- |
|- |
||
| align="right" | 18 |
| align="right" | 18 |
||
Line 136: | Line 137: | ||
| align="right" | 259117086…909315071 |
| align="right" | 259117086…909315071 |
||
| align="right" | 969 |
| align="right" | 969 |
||
| |
| September 8 1957 |
||
| |
| Hans Riesel|Riesel |
||
|- |
|- |
||
| align="right" | 19 |
| align="right" | 19 |
||
Line 143: | Line 144: | ||
| align="right" | 190797007…350484991 |
| align="right" | 190797007…350484991 |
||
| align="right" | 1,281 |
| align="right" | 1,281 |
||
| |
| November 3 1961 |
||
| |
| Alexander Hurwitz|Hurwitz |
||
|- |
|- |
||
| align="right" | 20 |
| align="right" | 20 |
||
Line 150: | Line 151: | ||
| align="right" | 285542542…608580607 |
| align="right" | 285542542…608580607 |
||
| align="right" | 1,332 |
| align="right" | 1,332 |
||
| |
| November 3 1961 |
||
| |
| Alexander Hurwitz|Hurwitz |
||
|- |
|- |
||
| align="right" | 21 |
| align="right" | 21 |
||
Line 157: | Line 158: | ||
| align="right" | 478220278…225754111 |
| align="right" | 478220278…225754111 |
||
| align="right" | 2,917 |
| align="right" | 2,917 |
||
| |
| May 11 1963 |
||
| |
| Donald B. Gillies|Gillies |
||
|- |
|- |
||
| align="right" | 22 |
| align="right" | 22 |
||
Line 164: | Line 165: | ||
| align="right" | 346088282…789463551 |
| align="right" | 346088282…789463551 |
||
| align="right" | 2,993 |
| align="right" | 2,993 |
||
| |
| May 16 1963 |
||
| |
| Donald B. Gillies|Gillies |
||
|- |
|- |
||
| align="right" | 23 |
| align="right" | 23 |
||
Line 171: | Line 172: | ||
| align="right" | 281411201…696392191 |
| align="right" | 281411201…696392191 |
||
| align="right" | 3,376 |
| align="right" | 3,376 |
||
| |
| June 2 1963 |
||
| |
| Donald B. Gillies|Gillies |
||
|- |
|- |
||
| align="right" | 24 |
| align="right" | 24 |
||
Line 178: | Line 179: | ||
| align="right" | 431542479…968041471 |
| align="right" | 431542479…968041471 |
||
| align="right" | 6,002 |
| align="right" | 6,002 |
||
| |
| March 4 1971 |
||
| |
| Bryant Tuckerman|Tuckerman |
||
|- |
|- |
||
| align="right" | 25 |
| align="right" | 25 |
||
Line 185: | Line 186: | ||
| align="right" | 448679166…511882751 |
| align="right" | 448679166…511882751 |
||
| align="right" | 6,533 |
| align="right" | 6,533 |
||
| |
| October 30 1978 |
||
| |
| Landon Curt Noll|Noll & Laura Nickel|Nickel |
||
|- |
|- |
||
| align="right" | 26 |
| align="right" | 26 |
||
Line 192: | Line 193: | ||
| align="right" | 402874115…779264511 |
| align="right" | 402874115…779264511 |
||
| align="right" | 6,987 |
| align="right" | 6,987 |
||
| |
| February 9 1979 |
||
| |
| Landon Curt Noll|Noll |
||
|- |
|- |
||
| align="right" | 27 |
| align="right" | 27 |
||
Line 199: | Line 200: | ||
| align="right" | 854509824…011228671 |
| align="right" | 854509824…011228671 |
||
| align="right" | 13,395 |
| align="right" | 13,395 |
||
| |
| April 8 1979 |
||
| |
| Harry Nelson|Nelson & David Slowinski|Slowinski |
||
|- |
|- |
||
| align="right" | 28 |
| align="right" | 28 |
||
Line 206: | Line 207: | ||
| align="right" | 536927995…433438207 |
| align="right" | 536927995…433438207 |
||
| align="right" | 25,962 |
| align="right" | 25,962 |
||
| |
| September 25 1982 |
||
| |
| David Slowinski|Slowinski |
||
|- |
|- |
||
| align="right" | 29 |
| align="right" | 29 |
||
Line 213: | Line 214: | ||
| align="right" | 521928313…465515007 |
| align="right" | 521928313…465515007 |
||
| align="right" | 33,265 |
| align="right" | 33,265 |
||
| |
| January 28 1988 |
||
| |
| Walt Colquitt|Colquitt & Luke Welsh|Welsh |
||
|- |
|- |
||
| align="right" | 30 |
| align="right" | 30 |
||
Line 220: | Line 221: | ||
| align="right" | 512740276…730061311 |
| align="right" | 512740276…730061311 |
||
| align="right" | 39,751 |
| align="right" | 39,751 |
||
| |
| September 19 1983[http://www.isthe.com/chongo/tech/math/prime/mersenne.html#largest] |
||
| |
| David Slowinski|Slowinski |
||
|- |
|- |
||
| align="right" | 31 |
| align="right" | 31 |
||
Line 227: | Line 228: | ||
| align="right" | 746093103…815528447 |
| align="right" | 746093103…815528447 |
||
| align="right" | 65,050 |
| align="right" | 65,050 |
||
| |
| September 1 1985[http://www.isthe.com/chongo/tech/math/prime/mersenne.html#largest] |
||
| |
| David Slowinski|Slowinski |
||
|- |
|- |
||
| align="right" | 32 |
| align="right" | 32 |
||
Line 234: | Line 235: | ||
| align="right" | 174135906…544677887 |
| align="right" | 174135906…544677887 |
||
| align="right" | 227,832 |
| align="right" | 227,832 |
||
| |
| February 19 1992 |
||
| |
| David Slowinski|Slowinski & Paul Gage|Gage on Harwell Lab Cray-2 [http://primes.utm.edu/notes/756839.html] |
||
|- |
|- |
||
| align="right" | 33 |
| align="right" | 33 |
||
Line 241: | Line 242: | ||
| align="right" | 129498125…500142591 |
| align="right" | 129498125…500142591 |
||
| align="right" | 258,716 |
| align="right" | 258,716 |
||
| |
| January 4 1994 [http://www.math.unicaen.fr/~reyssat/largest.html] |
||
| |
| David Slowinski|Slowinski & Paul Gage|Gage |
||
|- |
|- |
||
| align="right" | 34 |
| align="right" | 34 |
||
Line 248: | Line 249: | ||
| align="right" | 412245773…089366527 |
| align="right" | 412245773…089366527 |
||
| align="right" | 378,632 |
| align="right" | 378,632 |
||
| |
| September 3 1996 |
||
| |
| David Slowinski|Slowinski & Paul Gage|Gage [http://primes.utm.edu/notes/1257787.html] |
||
|- |
|- |
||
| align="right" | 35 |
| align="right" | 35 |
||
Line 255: | Line 256: | ||
| align="right" | 814717564…451315711 |
| align="right" | 814717564…451315711 |
||
| align="right" | 420,921 |
| align="right" | 420,921 |
||
| |
| November 13 1996 |
||
| |
| Great Internet Mersenne Prime Search|GIMPS / Joel Armengaud [http://www.mersenne.org/1398269.htm] |
||
|- |
|- |
||
| align="right" | 36 |
| align="right" | 36 |
||
Line 262: | Line 263: | ||
| align="right" | 623340076…729201151 |
| align="right" | 623340076…729201151 |
||
| align="right" | 895,932 |
| align="right" | 895,932 |
||
| |
| August 24 1997 |
||
| |
| Great Internet Mersenne Prime Search|GIMPS / Gordon Spence [http://www.mersenne.org/2976221.htm] |
||
|- |
|- |
||
| align="right" | 37 |
| align="right" | 37 |
||
Line 269: | Line 270: | ||
| align="right" | 127411683…024694271 |
| align="right" | 127411683…024694271 |
||
| align="right" | 909,526 |
| align="right" | 909,526 |
||
| |
| January 27 1998 |
||
| |
| Great Internet Mersenne Prime Search|GIMPS / Roland Clarkson [http://www.mersenne.org/3021377.htm] |
||
|- |
|- |
||
| align="right" | 38 |
| align="right" | 38 |
||
Line 276: | Line 277: | ||
| align="right" | 437075744…924193791 |
| align="right" | 437075744…924193791 |
||
| align="right" | 2,098,960 |
| align="right" | 2,098,960 |
||
| |
| June 1 1999 |
||
| |
| Great Internet Mersenne Prime Search|GIMPS / Nayan Hajratwala [http://www.mersenne.org/6972593.htm] |
||
|- |
|- |
||
| align="right" | 39 |
| align="right" | 39 |
||
Line 283: | Line 284: | ||
| align="right" | 924947738…256259071 |
| align="right" | 924947738…256259071 |
||
| align="right" | 4,053,946 |
| align="right" | 4,053,946 |
||
| |
| November 14 2001 |
||
| |
| Great Internet Mersenne Prime Search|GIMPS / Michael Cameron [http://www.mersenne.org/13466917.htm] |
||
|- |
|- |
||
| align="right" | 40<sup>*</sup> |
| align="right" | 40<sup>*</sup> |
||
Line 290: | Line 291: | ||
| align="right" | 125976895…855682047 |
| align="right" | 125976895…855682047 |
||
| align="right" | 6,320,430 |
| align="right" | 6,320,430 |
||
| |
| November 17 2003 |
||
| |
| Great Internet Mersenne Prime Search|GIMPS / Michael Shafer [http://www.mersenne.org/20996011.htm] |
||
|- |
|- |
||
| align="right" | 41<sup>*</sup> |
| align="right" | 41<sup>*</sup> |
||
Line 297: | Line 298: | ||
| align="right" | 299410429…733969407 |
| align="right" | 299410429…733969407 |
||
| align="right" | 7,235,733 |
| align="right" | 7,235,733 |
||
| |
| May 15 2004 |
||
| |
| Great Internet Mersenne Prime Search|GIMPS / Josh Findley [http://www.mersenne.org/24036583.htm] |
||
|- |
|- |
||
| align="right" | 42<sup>*</sup> |
| align="right" | 42<sup>*</sup> |
||
Line 304: | Line 305: | ||
| align="right" | 122164630…577077247 |
| align="right" | 122164630…577077247 |
||
| align="right" | 7,816,230 |
| align="right" | 7,816,230 |
||
| |
| February 18 2005 |
||
| |
| Great Internet Mersenne Prime Search|GIMPS / Martin Nowak [http://www.mersenne.org/25964951.htm] |
||
|- |
|- |
||
| align="right" | 43<sup>*</sup> |
| align="right" | 43<sup>*</sup> |
||
Line 311: | Line 312: | ||
| align="right" | 315416475…652943871 |
| align="right" | 315416475…652943871 |
||
| align="right" | 9,152,052 |
| align="right" | 9,152,052 |
||
| |
| December 15 2005 |
||
| |
| Great Internet Mersenne Prime Search|GIMPS / Curtis Cooper (mathematician)|Curtis Cooper & Steven Boone [http://www.mersenne.org/30402457.htm] |
||
|- |
|- |
||
| align="right" | 44<sup>*</sup> |
| align="right" | 44<sup>*</sup> |
||
Line 318: | Line 319: | ||
| align="right" | 124575026…053967871 |
| align="right" | 124575026…053967871 |
||
| align="right" | 9,808,358 |
| align="right" | 9,808,358 |
||
| |
| September 4 2006 |
||
| |
| Great Internet Mersenne Prime Search|GIMPS / Curtis Cooper (mathematician)|Curtis Cooper & Steven Boone [http://www.mersenne.org/32582657.htm] |
||
|} |
|} |
||
== Java precision == |
|||
:The 45th and 46th Mersenne primes have been discovered, is the intention to keep this table up to date? --[[User:Lupus|Lupus]] 17:24, 2 December 2008 (UTC) |
|||
:: The above list seems to be copied ''in toto'' from the updated Wikipedia site: |
|||
<big> https://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes </big> |
|||
:: The above Wikipedia site now has a list of '''51''' Mersenne primes. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 19:57, 7 May 2019 (UTC) |
|||
== Java precision == |
|||
The Java version is still limited by types. Integer.parseInt(args[0]) limits p to 2147483647. Also the fact that isMersennePrime takes an int limits it there too. For full arbitrary precision every int needs to be a BigInteger or BigDecimal and a square root method will need to be created for them. The limitation is OK I think (I don't think we'll be getting up to 2<sup>2147483647</sup> - 1 anytime soon), but the claim "any arbitrary prime" is false because of the use of ints. --[[User:Mwn3d|Mwn3d]] 07:45, 21 February 2008 (MST) |
The Java version is still limited by types. Integer.parseInt(args[0]) limits p to 2147483647. Also the fact that isMersennePrime takes an int limits it there too. For full arbitrary precision every int needs to be a BigInteger or BigDecimal and a square root method will need to be created for them. The limitation is OK I think (I don't think we'll be getting up to 2<sup>2147483647</sup> - 1 anytime soon), but the claim "any arbitrary prime" is false because of the use of ints. --[[User:Mwn3d|Mwn3d]] 07:45, 21 February 2008 (MST) |
||
== Speeding things up == |
|||
The main loop in Lucas-Lehmer is doing (n*n) mod M where M=2^p-1, and p > 1. '''But we can do it without division'''. |
|||
<lang>We compute the remainder of a division by M. Now, intuitively, dividing by 2^p-1 is almost |
|||
like dividing by 2^p, except the latter is much faster since it's a shift. |
|||
Let's compute how much the two divisions differ. |
|||
We will call S = n*n. Notice that since the remainder mod M is computed again and again, the value of n must be < M at |
|||
the beginning of a loop, that is at most 2^p-2, thus S = n*n <= 2^(2*p) - 4*2^p + 4 = 2^p * (2^p - 2) + 4 - 2*2^p |
|||
When dividing S by M, you get quotient q1 and remainder r1 with S = q1*M + r1 and 0 <= r1 < M |
|||
When dividing S by M+1, you get likewise S = q2*(M+1) + r2 and 0 <= r2 <= M |
|||
In the latter, we divide by a larger number, so the quotient must be less, or maybe equal, that is, q2 <= q1. |
|||
Subtract the two equalities, giving |
|||
0 = (q2 - q1)*M + q2 + r2 - r1 |
|||
(q1 - q2)*M = q2 + r2 - r1 |
|||
Since S = 2^p * (2^p - 2) + 4 - 2*2^p |
|||
<= 2^p * (2^p - 2), |
|||
then the quotient q2 is less than 2^p - 2 (remember, when computing q2, we divide by M+1 = 2^p). |
|||
Now, 0 <= q2 <= 2^p - 2 |
|||
0 <= r2 <= 2^p - 1 |
|||
0 <= r1 <= 2^p - 2 |
|||
Thus the right hand side is >= 0, and <= 2*2^p - 3. |
|||
The left hand side is a multiple of M = 2^p - 1. |
|||
Therefore, this multiple must be 0*M or 1*M, certainly not 2*M = 2*2^p - 2, |
|||
which would be > 2*2^p - 3, and not any other higher multiple would do. |
|||
So we have proved that q1 - q2 = 0 or 1. |
|||
This means that division by 2^p is almost equivalent (regarding the quotient) |
|||
to dividing by 2^p-1: it's the same quotient, or maybe too short by 1. |
|||
Now, the remainder S mod M. |
|||
We start with a quotient q = S div 2^p, or simply q = S >> p (right shift). |
|||
The remainder is S - q*M = S - q*(2^p - 1) = S - q*2^p + q, and the multiplication by 2^p is a left shift. |
|||
And this remainder may be a bit too large, if our quotient is a bit too small (by one): in this case we must subtract M. |
|||
So, in pseudo-code, we are done if we do: |
|||
S = n*n |
|||
q = S >> p |
|||
r = S - (q << p) + q |
|||
if r >= M then r = r - M |
|||
We can go a bit further: taking S >> p then q << p is simply keeping the higher bits of S. |
|||
But then we subtract these higher bits from S, so we only keep the lower bits, |
|||
that is we do (S & mask), and this mask is simply M ! (remember, M = 2^p - 1, a bit mask of p bits equal to "1") |
|||
The pseudo-code can thus be written |
|||
S = n*n |
|||
r = (S & M) + (S >> p) |
|||
if r >= M then r = r - M |
|||
And we have computed a remainder mod M without any division, only a few addition/subtraction/shift/bitwise-and, |
|||
which will be much faster (each has a linear time complexity). |
|||
How much faster ? For exponents between 1 and 2000, in Python, the job is done 2.87 times as fast. |
|||
For exponents between 1 and 5000, it's 3.42 times as fast. And it gets better and better, since the comlexity is lower. |
|||
</lang> |
|||
[[User:Arbautjc|Arbautjc]] ([[User talk:Arbautjc|talk]]) 22:04, 15 November 2013 (UTC) |
|||
May 2015 - fixed small bugs in both Python implementations. In the first, execution failed (Python 3) without a cast to int in the test. In the second, there was a typo - an 'r' should have been 's'. |
|||
: Timing for some solutions for 2..11213: |
|||
{| class="wikitable" |
|||
|- |
|||
! Time (s) |
|||
! Solution |
|||
|- |
|||
| 871.2 |
|||
| Python without optimizations |
|||
|- |
|||
| 314.7 |
|||
| Python with optimizations |
|||
|- |
|||
| 124.7 |
|||
| Perl Math::GMP without optimizations |
|||
|- |
|||
| 106.9 |
|||
| Pari/GP 2.8.0 |
|||
|- |
|||
| 61.8 |
|||
| Perl Math::GMP with optimization |
|||
|- |
|||
| 33.0 |
|||
| Python using gmpy2 (skipping non-primes) |
|||
|- |
|||
| 14.2 |
|||
| C/GMP with even more optimizations |
|||
|- |
|||
| 13.3 |
|||
| Perl Math::Prime::Util::GMP (source of C/GMP code) |
|||
|} |
|||
[[User:Danaj|Danaj]] ([[User talk:Danaj|talk]]) 19:49, 9 May 2015 (UTC) |
|||
Rust solution for 2..11213 -> 8.6 s |
|||
Pari/GP solution for 2..11213 -> 2.835 s --[[User:Nebulus|Nebulus]] ([[User talk:Nebulus|talk]]) 05:21, 22 February 2023 (UTC) |
Latest revision as of 05:22, 22 February 2023
M23,209 is 36 CPU hours ≡ 1979
Welcome to 1979!
- Yeah. I know. :-) --Short Circuit 07:55, 21 February 2008 (MST)
List of known Mersenne primes
The table below lists all known Mersenne primes:
# | n | Mn | Digits in Mn | Date of discovery | Discoverer |
---|---|---|---|---|---|
1 | 2 | 3 (number)|3 | 1 | ancient | ancient |
2 | 3 | 7 (number)|7 | 1 | ancient | ancient |
3 | 5 | 31 (number)|31 | 2 | ancient | ancient |
4 | 7 | 127 (number)|127 | 3 | ancient | ancient |
5 | 13 | 8191 | 4 | 1456 | anonymous [1] |
6 | 17 | 131071 | 6 | 1588 | Cataldi |
7 | 19 | 524287 | 6 | 1588 | Cataldi |
8 | 31 | 2147483647 | 10 | 1772 | Euler |
9 | 61 | 2305843009213693951 | 19 | 1883 | Pervushin |
10 | 89 | 618970019…449562111 | 27 | 1911 | Powers |
11 | 107 | 162259276…010288127 | 33 | 1914 | Powers[2] |
12 | 127 | 170141183…884105727 | 39 | 1876 | Lucas |
13 | 521 | 686479766…115057151 | 157 | January 30 1952 | Robinson |
14 | 607 | 531137992…031728127 | 183 | January 30 1952 | Robinson |
15 | 1,279 | 104079321…168729087 | 386 | June 25 1952 | Robinson |
16 | 2,203 | 147597991…697771007 | 664 | October 7 1952 | Robinson |
17 | 2,281 | 446087557…132836351 | 687 | October 9 1952 | Robinson |
18 | 3,217 | 259117086…909315071 | 969 | September 8 1957 | Riesel |
19 | 4,253 | 190797007…350484991 | 1,281 | November 3 1961 | Hurwitz |
20 | 4,423 | 285542542…608580607 | 1,332 | November 3 1961 | Hurwitz |
21 | 9,689 | 478220278…225754111 | 2,917 | May 11 1963 | Gillies |
22 | 9,941 | 346088282…789463551 | 2,993 | May 16 1963 | Gillies |
23 | 11,213 | 281411201…696392191 | 3,376 | June 2 1963 | Gillies |
24 | 19,937 | 431542479…968041471 | 6,002 | March 4 1971 | Tuckerman |
25 | 21,701 | 448679166…511882751 | 6,533 | October 30 1978 | Noll & Laura Nickel|Nickel |
26 | 23,209 | 402874115…779264511 | 6,987 | February 9 1979 | Noll |
27 | 44,497 | 854509824…011228671 | 13,395 | April 8 1979 | Nelson & David Slowinski|Slowinski |
28 | 86,243 | 536927995…433438207 | 25,962 | September 25 1982 | Slowinski |
29 | 110,503 | 521928313…465515007 | 33,265 | January 28 1988 | Colquitt & Luke Welsh|Welsh |
30 | 132,049 | 512740276…730061311 | 39,751 | September 19 1983[3] | Slowinski |
31 | 216,091 | 746093103…815528447 | 65,050 | September 1 1985[4] | Slowinski |
32 | 756,839 | 174135906…544677887 | 227,832 | February 19 1992 | Slowinski & Paul Gage|Gage on Harwell Lab Cray-2 [5] |
33 | 859,433 | 129498125…500142591 | 258,716 | January 4 1994 [6] | Slowinski & Paul Gage|Gage |
34 | 1,257,787 | 412245773…089366527 | 378,632 | September 3 1996 | Slowinski & Paul Gage|Gage [7] |
35 | 1,398,269 | 814717564…451315711 | 420,921 | November 13 1996 | GIMPS / Joel Armengaud [8] |
36 | 2,976,221 | 623340076…729201151 | 895,932 | August 24 1997 | GIMPS / Gordon Spence [9] |
37 | 3,021,377 | 127411683…024694271 | 909,526 | January 27 1998 | GIMPS / Roland Clarkson [10] |
38 | 6,972,593 | 437075744…924193791 | 2,098,960 | June 1 1999 | GIMPS / Nayan Hajratwala [11] |
39 | 13,466,917 | 924947738…256259071 | 4,053,946 | November 14 2001 | GIMPS / Michael Cameron [12] |
40* | 20,996,011 | 125976895…855682047 | 6,320,430 | November 17 2003 | GIMPS / Michael Shafer [13] |
41* | 24,036,583 | 299410429…733969407 | 7,235,733 | May 15 2004 | GIMPS / Josh Findley [14] |
42* | 25,964,951 | 122164630…577077247 | 7,816,230 | February 18 2005 | GIMPS / Martin Nowak [15] |
43* | 30,402,457 | 315416475…652943871 | 9,152,052 | December 15 2005 | GIMPS / Curtis Cooper (mathematician)|Curtis Cooper & Steven Boone [16] |
44* | 32,582,657 | 124575026…053967871 | 9,808,358 | September 4 2006 | GIMPS / Curtis Cooper (mathematician)|Curtis Cooper & Steven Boone [17] |
- The 45th and 46th Mersenne primes have been discovered, is the intention to keep this table up to date? --Lupus 17:24, 2 December 2008 (UTC)
- The above list seems to be copied in toto from the updated Wikipedia site:
https://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes
- The above Wikipedia site now has a list of 51 Mersenne primes. -- Gerard Schildberger (talk) 19:57, 7 May 2019 (UTC)
Java precision
The Java version is still limited by types. Integer.parseInt(args[0]) limits p to 2147483647. Also the fact that isMersennePrime takes an int limits it there too. For full arbitrary precision every int needs to be a BigInteger or BigDecimal and a square root method will need to be created for them. The limitation is OK I think (I don't think we'll be getting up to 22147483647 - 1 anytime soon), but the claim "any arbitrary prime" is false because of the use of ints. --Mwn3d 07:45, 21 February 2008 (MST)
Speeding things up
The main loop in Lucas-Lehmer is doing (n*n) mod M where M=2^p-1, and p > 1. But we can do it without division.
<lang>We compute the remainder of a division by M. Now, intuitively, dividing by 2^p-1 is almost like dividing by 2^p, except the latter is much faster since it's a shift. Let's compute how much the two divisions differ.
We will call S = n*n. Notice that since the remainder mod M is computed again and again, the value of n must be < M at the beginning of a loop, that is at most 2^p-2, thus S = n*n <= 2^(2*p) - 4*2^p + 4 = 2^p * (2^p - 2) + 4 - 2*2^p
When dividing S by M, you get quotient q1 and remainder r1 with S = q1*M + r1 and 0 <= r1 < M When dividing S by M+1, you get likewise S = q2*(M+1) + r2 and 0 <= r2 <= M In the latter, we divide by a larger number, so the quotient must be less, or maybe equal, that is, q2 <= q1.
Subtract the two equalities, giving 0 = (q2 - q1)*M + q2 + r2 - r1 (q1 - q2)*M = q2 + r2 - r1
Since S = 2^p * (2^p - 2) + 4 - 2*2^p
<= 2^p * (2^p - 2),
then the quotient q2 is less than 2^p - 2 (remember, when computing q2, we divide by M+1 = 2^p).
Now, 0 <= q2 <= 2^p - 2
0 <= r2 <= 2^p - 1 0 <= r1 <= 2^p - 2
Thus the right hand side is >= 0, and <= 2*2^p - 3. The left hand side is a multiple of M = 2^p - 1.
Therefore, this multiple must be 0*M or 1*M, certainly not 2*M = 2*2^p - 2, which would be > 2*2^p - 3, and not any other higher multiple would do. So we have proved that q1 - q2 = 0 or 1.
This means that division by 2^p is almost equivalent (regarding the quotient) to dividing by 2^p-1: it's the same quotient, or maybe too short by 1.
Now, the remainder S mod M. We start with a quotient q = S div 2^p, or simply q = S >> p (right shift). The remainder is S - q*M = S - q*(2^p - 1) = S - q*2^p + q, and the multiplication by 2^p is a left shift. And this remainder may be a bit too large, if our quotient is a bit too small (by one): in this case we must subtract M.
So, in pseudo-code, we are done if we do:
S = n*n q = S >> p r = S - (q << p) + q if r >= M then r = r - M
We can go a bit further: taking S >> p then q << p is simply keeping the higher bits of S. But then we subtract these higher bits from S, so we only keep the lower bits, that is we do (S & mask), and this mask is simply M ! (remember, M = 2^p - 1, a bit mask of p bits equal to "1")
The pseudo-code can thus be written
S = n*n r = (S & M) + (S >> p) if r >= M then r = r - M
And we have computed a remainder mod M without any division, only a few addition/subtraction/shift/bitwise-and, which will be much faster (each has a linear time complexity).
How much faster ? For exponents between 1 and 2000, in Python, the job is done 2.87 times as fast. For exponents between 1 and 5000, it's 3.42 times as fast. And it gets better and better, since the comlexity is lower. </lang> Arbautjc (talk) 22:04, 15 November 2013 (UTC)
May 2015 - fixed small bugs in both Python implementations. In the first, execution failed (Python 3) without a cast to int in the test. In the second, there was a typo - an 'r' should have been 's'.
- Timing for some solutions for 2..11213:
Time (s) | Solution |
---|---|
871.2 | Python without optimizations |
314.7 | Python with optimizations |
124.7 | Perl Math::GMP without optimizations |
106.9 | Pari/GP 2.8.0 |
61.8 | Perl Math::GMP with optimization |
33.0 | Python using gmpy2 (skipping non-primes) |
14.2 | C/GMP with even more optimizations |
13.3 | Perl Math::Prime::Util::GMP (source of C/GMP code) |
Danaj (talk) 19:49, 9 May 2015 (UTC)
Rust solution for 2..11213 -> 8.6 s
Pari/GP solution for 2..11213 -> 2.835 s --Nebulus (talk) 05:21, 22 February 2023 (UTC)