MathWorld Headline News
45th and 46th Mersenne Primes Found
By Eric W. Weisstein
September 16, 2008--Two years after the 44th Mersenne prime was reported (MathWorld headline news: September 11, 2006), the Great Internet Mersenne Prime Search (GIMPS) project has discovered the 45th and 46th known Mersenne primes. The discoveries were made by Edson Smith on August 23, 2008 (for the larger prime) and Hans-Michael Elvenich on September 6, 2008 (for the smaller prime), and announced by GIMPS organizer George Woltman on September 16. As with the previous Mersenne prime discovery (in which Dr. Curtis Cooper and Dr. Steven Boone who at staggering odds, were also the discoverers of the 43rd known Mersenne prime), thus proving that lightning not only strikes twice, it can double-strike tiwce! Additional details can be found in the Mersenne.org press release.
Mersenne numbers are numbers of the form Mn = 2n - 1, giving the first few as 1, 3, 7, 15, 31, 63, 127, .... Interestingly, the definition of these numbers therefore means that the nth Mersenne number is simply a string of n 1s when represented in binary. For example, M7 = 27 - 1 = 127 = 11111112 is a Mersenne number. Mersenne primes are Mersenne numbers that are also prime, i.e., have no factors other than 1 and themselves. So, since the number 127 is prime and is a Mersenne number, it is a Mersenne prime.
The new Mersenne primes are 237,156,667 - 1 = 20225440689097733553...21340265022308220927 and 243,112,609 - 1 = 31647026933025592314...80022181166697152511 (where the ellipsis indicates that several million intervening digits have been omitted for conciseness) and have a whopping total of 11,185,272 and 12,978,189 decimal digits, respectively. Both primes therefore are not only the largest known Mersenne primes, but also the largest known primes of any kind. In fact, there is a particularly efficient and, more importantly, deterministic primality test for Mersenne numbers known as the Lucas-Lehmer test. The efficiency of this test combined with the high historical profile of the Mersenne numbers thus accounts for the fact that the eight largest known primes are all Mersenne primes (prime database).
For those curious to see the new primes in their full 11,185,272 and 12,978,189 digits of glory, the results of a short Mathematica calculation generating their decimal digits are available by downloading the notebooks mersenne45.nb and mersenne46.nb. If you do not own Mathematica, you can download a free player version to view this file. A poster featuring all 12.9 million digits of the new prime (displayed in an extremely small point size) created by Richard Crandall, discoverer of the advanced transform algorithm used by the GIMPS program, is (or will shortly be) available from Perfectly Scientific.
The twelve largest known Mersenne primes (including the latest) have all been discovered by GIMPS, which is a distributed computing project being undertaken by an international collaboration of volunteers. Thus far, GIMPS participants have tested and double-checked all exponents n below 17,001,247, while all exponents below 21,842,101 have been tested at least once.
The study of such numbers has a long and interesting history, and the search for Mersenne numbers that are prime has been a computationally challenging exercise requiring the world's fastest computers. Mersenne primes are intimately connected with so-called perfect numbers, which were extensively studied by the ancient Greeks, including by Euclid. A complete list of indices n of the previously known Mersenne primes is given in the table below (as well as by sequence A000043 in Neil Sloane's On-Line Encyclopedia of Integer Sequences). However, note that the region after the 40th known Mersenne primes has not been completely searched, so while the 41st number listed is the 41st Mersenne prime discovered to date, it is not yet known if M24,036,583 is actually the 41st Mersenne prime.
# | n | digits | year | discoverer (reference) |
1 | 2 | 1 | antiquity | |
2 | 3 | 1 | antiquity | |
3 | 5 | 2 | antiquity | |
4 | 7 | 3 | antiquity | |
5 | 13 | 4 | 1461 | Reguis (1536), Cataldi (1603) |
6 | 17 | 6 | 1588 | Cataldi (1603) |
7 | 19 | 6 | 1588 | Cataldi (1603) |
8 | 31 | 10 | 1750 | Euler (1772) |
9 | 61 | 19 | 1883 | Pervouchine (1883), Seelhoff (1886) |
10 | 89 | 27 | 1911 | Powers (1911) |
11 | 107 | 33 | 1913 | Powers (1914) |
12 | 127 | 39 | 1876 | Lucas (1876) |
13 | 521 | 157 | Jan. 30, 1952 | Robinson |
14 | 607 | 183 | Jan. 30, 1952 | Robinson |
15 | 1279 | 386 | Jan. 30, 1952 | Robinson |
16 | 2203 | 664 | Jan. 30, 1952 | Robinson |
17 | 2281 | 687 | Jan. 30, 1952 | Robinson |
18 | 3217 | 969 | Sep. 8, 1957 | Riesel |
19 | 4253 | 1281 | Nov. 3, 1961 | Hurwitz |
20 | 4423 | 1332 | Nov. 3, 1961 | Hurwitz |
21 | 9689 | 2917 | May 11, 1963 | Gillies (1964) |
22 | 9941 | 2993 | May 16, 1963 | Gillies (1964) |
23 | 11213 | 3376 | Jun. 2, 1963 | Gillies (1964) |
24 | 19937 | 6002 | Mar. 4, 1971 | Tuckerman (1971) |
25 | 21701 | 6533 | Oct. 30, 1978 | Noll and Nickel (1980) |
26 | 23209 | 6987 | Feb. 9, 1979 | Noll (Noll and Nickel 1980) |
27 | 44497 | 13395 | Apr. 8, 1979 | Nelson and Slowinski (Slowinski 1978-79) |
28 | 86243 | 25962 | Sep. 25, 1982 | Slowinski |
29 | 110503 | 33265 | Jan. 28, 1988 | Colquitt and Welsh (1991) |
30 | 132049 | 39751 | Sep. 20, 1983 | Slowinski |
31 | 216091 | 65050 | Sep. 6, 1985 | Slowinski |
32 | 756839 | 227832 | Feb. 19, 1992 | Slowinski and Gage |
33 | 859433 | 258716 | Jan. 10, 1994 | Slowinski and Gage |
34 | 1257787 | 378632 | Sep. 3, 1996 | Slowinski and Gage |
35 | 1398269 | 420921 | Nov. 12, 1996 | Joel Armengaud/GIMPS |
36 | 2976221 | 895832 | Aug. 24, 1997 | Gordon Spence/GIMPS (Devlin 1997) |
37 | 3021377 | 909526 | Jan. 27, 1998 | Roland Clarkson/GIMPS |
38 | 6972593 | 2098960 | Jun. 1, 1999 | Nayan Hajratwala/GIMPS |
39 | 13466917 | 4053946 | Nov. 14, 2001 | Michael Cameron/GIMPS |
40 | 20996011 | 6320430 | Nov. 17, 2003 | Michael Shafer/GIMPS |
41? | 24036583 | 7235733 | May 15, 2004 | Josh Findley/GIMPS |
42? | 25964951 | 7816230 | Feb. 18, 2005 | Martin Nowak/GIMPS |
43? | 30402457 | 9152052 | Dec. 15, 2005 | Curtis Cooper and Steven Boone/GIMPS |
44? | 32582657 | 9808358 | Sep. 4, 2006 | Curtis Cooper and Steven Boone/GIMPS |
45? | 37156667 | 11185272 | Sep. 6, 2008 | Hans-Michael Elvenich/GIMPS |
46? | 43112609 | 12978189 | Aug. 23, 2008 | Edson Smith/GIMPS |
Caldwell, C. K. "The Largest Known Primes." http://www.utm.edu/research/primes/largest.html
GIMPS: The Great Internet Mersenne Prime Search. http://www.mersenne.org
GIMPS: The Great Internet Mersenne Prime Search Status. http://www.mersenne.org/status.htm
Mersenne.org. "MTitanic Primes Raced to Win $100,000 Research Award." Sep. 15, 2008. http://mersenne.org/m45and46.htm