Largest known prime number

From Wikipedia, the free encyclopedia
Jump to: navigation, search

As of August 2015, the largest known prime number is 257,885,161 − 1,[1] a number with 17,425,170 digits.

Plot of the number of digits in largest known prime by year, since the electronic computer. Note that the vertical scale is logarithmic. The red line is the exponential curve of best fit: y = exp(0.188439 t - 362.591), where t is in years.

Euclid proved that there is no largest prime number, so many mathematicians and hobbyists continue to search for large prime numbers.

Many of the largest known primes are Mersenne primes. As of February 2013 the ten largest known primes are Mersenne primes, while the eleventh is the largest known non-Mersenne prime.[2] The last 15 record primes were Mersenne primes.[2]

The fast Fourier transform implementation of the Lucas–Lehmer primality test for Mersenne numbers is fast compared to other known primality tests for other kinds of numbers.

The current record[edit]

The record is currently held by 257,885,161 − 1 with 17,425,170 digits. The value of it is

5818872662322464421751002121132323686363708523254215893257817044
... (17,425,042 digits omitted) ...
6822494937745410942833323095203705645658725746141988071724285951

The first and last 64 digits are shown above, with the intervening digits omitted.

Its discovery resulted from the Great Internet Mersenne Prime Search (GIMPS).

Prizes[edit]

There are several prizes offered by the Electronic Frontier Foundation for record primes.[3]

The record passed one million digits in 1999, earning a $50,000 prize.[4] In 2008 the record passed ten million digits, earning a $100,000 prize and a Cooperative Computing Award from the Electronic Frontier Foundation.[3] Time called it the 29th top invention of 2008.[5] Additional prizes are being offered for the first prime number found with at least one hundred million digits and the first with at least one billion digits.[3]

History[edit]

The following table lists the progression of the largest known prime number in ascending order. Here Mn= 2n − 1 is the Mersenne number with exponent n. The longest record-holder known was M19 = 524,287, which was the largest known prime for 144 years. No records are known before 1456.

Number # digits Year found Notes
M13 8,191 4 1456 Anonymous discovery: no proof provided, so sometimes not counted as a record.
M17 131,071 6 1460 Anonymous discovery: no proof provided. Later proven prime by Pietro Cataldi in 1588, and that is sometimes listed as a record.
M19 524,287 6 1588 Found by Pietro Cataldi
(232+1)/641 6,700,417 7 1732 Found by Leonhard Euler
M31 2,147,483,647 10 1772 Found by Leonhard Euler
(1018+1)/1000001 999,999,000,001 12 1851 Included (but question-marked) in a list of primes by Looff. Given his uncertainty, some do not include this as a record.
(264+1)/274177 67,280,421,310,721 14 1855 Found by Thomas Clausen, but proof was not provided: thus this record is not always listed.
[M59/179951] [3,203,431,780,337] [13] [1867] Found by Landry. A record of the immediately preceding entry is excluded.
M127 39 1876 Found by Édouard Lucas
(2148+1)/17 44 1951 Found by Ferrier; the largest record not set by computer.
180×(M127)2+1 79 1951 Using Cambridge's EDSAC computer
M521 157 1952
M607 183 1952
M1279 386 1952
M2203 664 1952
M2281 687 1952
M3217 969 1957
M4423 1,332 1961
M9689 2,917 1963
M9941 2,993 1963
M11213 3,376 1963
M19937 6,002 1971
M21701 6,533 1978
M23209 6,987 1979
M44497 13,395 1979
M86243 25,962 1982
M132049 39,751 1983
M216091 65,050 1985
391581×2216193−1 65,087 1989
M756839 227,832 1992
M859433 258,716 1994
M1257787 378,632 1996
M1398269 420,921 1996
M2976221 895,932 1997
M3021377 909,526 1998
M6972593 2,098,960 1999
M13466917 4,053,946 2001
M20996011 6,320,430 2003
M24036583 7,235,733 2004
M25964951 7,816,230 2005
M30402457 9,152,052 2005
M32582657 9,808,358 2006
M43112609 12,978,189 2008
M57885161 17,425,170 2013

The ten largest known prime numbers[edit]

Rank Prime number Found by Found date Number of digits Reference
1st 257,885,161 − 1 GIMPS 2013 January 25 17,425,170 [2]
2nd 243,112,609 − 1 GIMPS 2008 August 23 12,978,189 [2]
3rd 242,643,801 − 1 GIMPS 2009 April 12 12,837,064 [6]
4th 237,156,667 − 1 GIMPS 2008 September 6 11,185,272 [6]
5th 232,582,657 − 1 GIMPS 2006 September 4 9,808,358 [6]
6th 230,402,457 − 1 GIMPS 2005 December 15 9,152,052 [7]
7th 225,964,951 − 1 GIMPS 2005 February 18 7,816,230 [7]
8th 224,036,583 − 1 GIMPS 2004 May 15 7,235,733 [7]
9th 220,996,011 − 1 GIMPS 2003 November 17 6,320,430 [7]
10th 213,466,917 − 1 GIMPS 2001 November 14 4,053,946 [7]

GIMPS found the eleven latest records on ordinary computers operated by participants around the world.

The largest known prime that is not a Mersenne prime is 19249 × 213018586 + 1, found by Seventeen or Bust.[8] This is currently the eleventh largest known prime.

See also[edit]

References[edit]

  1. ^ "GIMPS Project Discovers Largest Known Prime Number, 257,885,161-1". Mersenne Research, Inc. 
  2. ^ a b c d Chris Caldwell, The largest known primes. Retrieved on 2013-02-05.
  3. ^ a b c "Record 12-Million-Digit Prime Number Nets $100,000 Prize". Electronic Frontier Foundation. Electronic Frontier Foundation. October 14, 2009. Retrieved November 26, 2011. 
  4. ^ Electronic Frontier Foundation, Big Prime Nets Big Prize.
  5. ^ "Best Inventions of 2008 - 29. The 46th Mersenne Prime". Time (Time Inc). October 29, 2008. Retrieved January 17, 2012. 
  6. ^ a b c Landon Curt Noll, Mersenne Prime Digits and Names. Retrieved on 2011-01-03.
  7. ^ a b c d e Samuel Yates, Chris Caldwell, The largest known primes. Retrieved on 2014-03-08.
  8. ^ "Press release, 5 May 2007". Seventeen or Bust. 

External links[edit]