**⚠️ Warning: This is a draft ⚠️**

This means it might contain formatting issues, incorrect code, conceptual problems, or other severe issues.

If you want to help to improve and eventually enable this page, please fork RosettaGit's repository and open a merge request on GitHub.

== M_{23,209} is 36 CPU hours ≡ 1979 ==
Welcome to 1979!
:Yeah. I know. :-) --[[User:Short Circuit|Short Circuit]] 07:55, 21 February 2008 (MST)

==List of known Mersenne primes==
The table below lists all known Mersenne primes:
{| class="wikitable"
|-
! #
! ''n''
! ''M''_{''n''}
! Digits in ''M''_{''n''}
! Date of discovery
! Discoverer
|-
| align="right" | 1
| align="right" | 2
| align="right" | 3 (number)|3
| align="right" | 1
| ''ancient''
| ''ancient''
|-
| align="right" | 2
| align="right" | 3
| align="right" | 7 (number)|7
| align="right" | 1
| ''ancient''
| ''ancient''
|-
| align="right" | 3
| align="right" | 5
| align="right" | 31 (number)|31
| align="right" | 2
| ''ancient''
| ''ancient''
|-
| align="right" | 4
| align="right" | 7
| align="right" | 127 (number)|127
| align="right" | 3
| ''ancient''
| ''ancient''
|-
| align="right" | 5
| align="right" | 13
| align="right" | 8191
| align="right" | 4
| 1456
| ''anonymous'' [http://primes.utm.edu/mersenne/]
|-
| align="right" | 6
| align="right" | 17
| align="right" | 131071
| align="right" | 6
| 1588
| Pietro Cataldi|Cataldi
|-
| align="right" | 7
| align="right" | 19
| align="right" | 524287
| align="right" | 6
| 1588
| Pietro Cataldi|Cataldi
|-
| align="right" | 8
| align="right" | 31
| align="right" | 2147483647
| align="right" | 10
| 1772
| Leonhard Euler|Euler
|-
| align="right" | 9
| align="right" | 61
| align="right" | 2305843009213693951
| align="right" | 19
| 1883
| Ivan Mikheevich Pervushin|Pervushin
|-
| align="right" | 10
| align="right" | 89
| align="right" | 618970019…449562111
| align="right" | 27
| 1911
| R. E. Powers|Powers
|-
| align="right" | 11
| align="right" | 107
| align="right" | 162259276…010288127
| align="right" | 33
| 1914
| R. E. Powers|Powers[http://primes.utm.edu/notes/fauquem.html]
|-
| align="right" | 12
| align="right" | 127
| align="right" | 170141183…884105727
| align="right" | 39
| 1876
| Edouard Lucas|Lucas
|-
| align="right" | 13
| align="right" | 521
| align="right" | 686479766…115057151
| align="right" | 157
| January 30 1952
| Raphael M. Robinson|Robinson
|-
| align="right" | 14
| align="right" | 607
| align="right" | 531137992…031728127
| align="right" | 183
| January 30 1952
| Raphael M. Robinson|Robinson
|-
| align="right" | 15
| align="right" | 1,279
| align="right" | 104079321…168729087
| align="right" | 386
| June 25 1952
| Raphael M. Robinson|Robinson
|-
| align="right" | 16
| align="right" | 2,203
| align="right" | 147597991…697771007
| align="right" | 664
| October 7 1952
| Raphael M. Robinson|Robinson
|-
| align="right" | 17
| align="right" | 2,281
| align="right" | 446087557…132836351
| align="right" | 687
| October 9 1952
| Raphael M. Robinson|Robinson
|-
| align="right" | 18
| align="right" | 3,217
| align="right" | 259117086…909315071
| align="right" | 969
| September 8 1957
| Hans Riesel|Riesel
|-
| align="right" | 19
| align="right" | 4,253
| align="right" | 190797007…350484991
| align="right" | 1,281
| November 3 1961
| Alexander Hurwitz|Hurwitz
|-
| align="right" | 20
| align="right" | 4,423
| align="right" | 285542542…608580607
| align="right" | 1,332
| November 3 1961
| Alexander Hurwitz|Hurwitz
|-
| align="right" | 21
| align="right" | 9,689
| align="right" | 478220278…225754111
| align="right" | 2,917
| May 11 1963
| Donald B. Gillies|Gillies
|-
| align="right" | 22
| align="right" | 9,941
| align="right" | 346088282…789463551
| align="right" | 2,993
| May 16 1963
| Donald B. Gillies|Gillies
|-
| align="right" | 23
| align="right" | 11,213
| align="right" | 281411201…696392191
| align="right" | 3,376
| June 2 1963
| Donald B. Gillies|Gillies
|-
| align="right" | 24
| align="right" | 19,937
| align="right" | 431542479…968041471
| align="right" | 6,002
| March 4 1971
| Bryant Tuckerman|Tuckerman
|-
| align="right" | 25
| align="right" | 21,701
| align="right" | 448679166…511882751
| align="right" | 6,533
| October 30 1978
| Landon Curt Noll|Noll & Laura Nickel|Nickel
|-
| align="right" | 26
| align="right" | 23,209
| align="right" | 402874115…779264511
| align="right" | 6,987
| February 9 1979
| Landon Curt Noll|Noll
|-
| align="right" | 27
| align="right" | 44,497
| align="right" | 854509824…011228671
| align="right" | 13,395
| April 8 1979
| Harry Nelson|Nelson & David Slowinski|Slowinski
|-
| align="right" | 28
| align="right" | 86,243
| align="right" | 536927995…433438207
| align="right" | 25,962
| September 25 1982
| David Slowinski|Slowinski
|-
| align="right" | 29
| align="right" | 110,503
| align="right" | 521928313…465515007
| align="right" | 33,265
| January 28 1988
| Walt Colquitt|Colquitt & Luke Welsh|Welsh
|-
| align="right" | 30
| align="right" | 132,049
| align="right" | 512740276…730061311
| 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" | 216,091
| align="right" | 746093103…815528447
| 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" | 756,839
| align="right" | 174135906…544677887
| 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" | 859,433
| align="right" | 129498125…500142591
| 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" | 1,257,787
| align="right" | 412245773…089366527
| 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" | 1,398,269
| align="right" | 814717564…451315711
| 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" | 2,976,221
| align="right" | 623340076…729201151
| 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" | 3,021,377
| align="right" | 127411683…024694271
| 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" | 6,972,593
| align="right" | 437075744…924193791
| 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" | 13,466,917
| align="right" | 924947738…256259071
| 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^{}*
| align="right" | 20,996,011
| align="right" | 125976895…855682047
| 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 ^{}*
| align="right" | 24,036,583
| align="right" | 299410429…733969407
| 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

^{}

*| align="right" | 25,964,951 | align="right" | 122164630…577077247 | 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*| align="right" | 30,402,457 | align="right" | 315416475…652943871 | 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

^{}^{*}| align="right" | 32,582,657 | align="right" | 124575026…053967871 | 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] |}

: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: https://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes :: 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^{2147483647} - 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'''.

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.

```
[[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
```