The Largest Known prime by Year: A Brief History

By Chris Caldwell

Thelargest known prime today is the 41,024,320 digitMersenne prime2^136279841-1 found in October 2024, but how big have the "largest known primes" been historically?  Historically, how have these primes been found?  We will briefly discuss each of these questions below.

Contents

1. Before Electronic Computers
   • Table of the Record Prime by Year
2. The Age of Electronic Computers
   • Graph of the Record Prime by Year
   • Table of the Record Prime by Year
3. Epilogue:No more predictions
   • The FirstBillion Digit Prime

  Part One: BeforeElectronic Computers

For information on the French Monk Marin Mersenne's prime conjecture and its errors,see this link

Many early writers felt (incorrectly) that ifp was prime, then so was M_p = 2^p-1.  These numbers, now called theMersenne Numbers, were the focus of most of the early searches for large primes.  The early history of these numbers is strewn with many false claims of primality, even by such notables as Mersenne, Leibniz, and Euler.  So we give credit to our first record holder with some doubt:

by 1588 Pietro Cataldi had correctly verified that 2¹⁷-1 = 131071 and 2¹⁹-1 = 524287 are both prime [Cataldi1603].

But Cataldi also had incorrectly stated 2ⁿ-1 was also prime for each of 23, 29, 31 and 37.  This is interesting because Cataldi made his discoveries by constructing what Shanks calls "the first extensive table of primes--up to 750" [Shanks78, p14].  These tables are big enough to show 2¹⁹-1 is prime (its square root is approximately 724) butnot large enough to handle these four larger numbers!

Note: Some writers (e.g., [Picutti1989] and [BS96, p309]) include the primes 8191=2¹³-1 (before 1458, Codice Palatino 573) and 131071=2¹⁷-1 (1460, Codex Ottb. Lat 3307) in their list of records.  But we omit them for lack of evidence that they were proven primes at that time, rather than just lucky guesses.

In 1640 Fermat showed that ifp is an odd prime, then all prime divisors of 2^p-1 have the form 2kp+1.  He then quickly showed Cataldi was wrong about 23 (which has the factor 47 withk=1) and 37 (factor 223 atk=3).  Finally, in 1738, Euler showed Cataldi was also wrong about 29 by finding the divisor 233.  Here, using Fermat's result,k=4.  This is just the second number to try using Fermat's result ask=2 andk=3 yield composites (so I would guess Fermat also knew of this factor).  Note that Cataldi's errors were shown with small factors found in Cataldi's own table of primes, and none took more than two trial divisions!

Euler gives us the first clear record (except perhaps for the date) by proving Cataldi was correct about 31:

by 1772 Euler had used clever reasoning and trial division to show 2³¹-1 = 2147483647 is prime.

The actual date must be between 28 October 1752 when Euler sent a letter to Goldbach [text fromEuler Archive] stating that he was uncertain about this number (even though he had earlier listed it as prime) and 1772 when a letter [text] was published from Euler to Bernoulli stating he proved 2³¹-1 prime by showing all prime divisors of 2³¹-1 must have one of the two forms 248n+1 and 248n+63, and then dividing by all such primes less than 46339 [Dickson19, pp18-19].  This requiresa simple theorem which is stronger than Fermat's result above.  (Euler had listed 2³¹-1 a prime as early as 1732, but he did so along with 2⁴¹-1 and 2⁴⁷-1 both of which were composite [translation].)

Note: Some writers (e.g., [BS96, p309]) include the primes 999999000001 (1851, "found" by Looff) and 67280421310721 (1 Jan. 1855, Clausen) in their tables.  The first appeared in a table of Looff with a question mark, but Reuschle [Reuschle1856, pp.3,18] claims Looff had proved it prime.  Thomas Clausen provided the factorization 274177 · 67280421310721 of 2⁶⁴+1 in a letter to Gauss dated 1 Jan 1855 stating both factors were prime [Biermann1964].  But it remains a claim without a method.

By 1867 Landry had found a larger prime, still by trial division, as a factor of 2⁵⁹-1 (namely (2⁵⁹-1)/179951 = 3203431780337), this prime held the record longer than any othernon-Mersenne would (before or after his discovery).  However all such efforts were to be eclipsed by a new mathematical discovery, so we pause for a moment to summarize all record primes (that I know about) before modern computers.  (In the long run, it is always the mathematics that decide how large of prime we can find.)

By 1876 Lucas had developed a clever test to determine if Mersenne numbers were prime.  His method was latermade even simpler by Lehmer in the 1930's, and is still used to discover the record primes!

In 1876 Lucas proved that 2¹²⁷-1 = 170141183460469231731687303715884105727 was prime.

"This remained the largest known prime until 1951" [HW79, p16] And this record, which stood for 75 years, may stand forever as the largest prime foundby hand calculations.

In 1951 Ferrier used a mechanical desk calculator and techniques based on partial inverses of Fermat's little theorem (see the pages onfinding and proving primes) to slightly better this record by finding a 44 digit prime:

In 1951 Ferrier found the prime (2¹⁴⁸+1)/17 = 20988936657440586486151264256610222593863921.

With this record we end the period before electronic computers, for in this same year a new record of 79 digits was to be set by computer.

Note: It is quite difficult to place Ferrier's discovery among Miller & Wheeler's chronologically.  We follow the traditional order and put Ferrier's first, butthere is good reason to doubt this.

For more information seeThe History of the Theory of Numbers by Leonard Dickson [Dickson19].

  Part Two:The Age of Electronic Computers

In 1951 Miller and Wheeler began the electronic computing age by finding several primes:

as well as the new 79 digit record:

180(M₁₂₇)²+1 (here M₁₂₇ = 2¹²⁷-1) [MW51].

This record was soon eclipsed by Raphael Robinson's discoveries of five new Mersennes the very next year using the SWAC (Standards Western Automatic Computer).  This was the first program that Robinson had ever written, and it ran the very first time he tried it! Not only that, but his program found two new record primes that very day!  He writes [Robinson54]:

The program was first tried on the SWAC on January 30, and two new primes were found that day [M₅₂₁, M₆₀₇], three other primes were found on June 25 [M₁₂₇₉], October 7 [M₂₂₀₃] and October 9 [M₂₂₈₁].

It is interesting to note that in 1949 the topologistM. H. A Newman used the prototype Manchester electronic computer (with 1024 bits of storage) to make the first attempt to find Mersenne primes by computer.  Perhaps becauseAlan Turing worked on this machine from 1948 to 1950, and improved the program by Newman, this first attempt at finding primes by (electronic) computers is sometimes attributed to him (e.g., [Robinson54] and [Ribenboim95, p93]).  The excellentAlan Turing Internet Scrapbook has a picture of this machine.

We see the records of Miller, Wheeler, and Robinson as the first points on the following graph--note the vertical scale!

Progress over the next few years was as steady as the increase in speed of computers.  Riesel found M₃₂₁₇ using the Swedish machine BESK; Hurwitz found M₄₂₅₃ and M₄₄₂₃ using an IBM 7090 (see next paragraph); Gillies used the ILLIAC-2 to find M₉₆₈₉, M₉₉₄₁ and M₁₁₂₁₃. Tuckerman found M₁₉₉₃₇ using an IBM360.

Surprisingly Hurwitz knew about M₄₄₂₃ seconds before M₄₂₅₃ (because of the way the output was stacked).  John Selfridge asked "Does a machine result need to be observed by a human before it can be said to be 'discovered'?"  To which Hurwitz replied, "forgetting about whether the computer knew, what if the computer operator who piled up the output looked?"  In the table below I decided that Hurwitz discovered the prime when he read the output, so M₄₂₅₃ was never the largest known prime.

Curiously the prime M_74207281 was detected by a machine months before a human noticed it--see the press release for this prime.

All of the Mersenne records were found using theLucas-Lehmer test and the other two were found usingProth's Theorem (or similar results).  TheAmdahl Six isJ Brown,C Noll,B Parady,G Smith,J Smith andS Zarantonello.

  Epilogue: No Predictions

When will we have a one billion digit prime? Good question! In the early days of the GIMPS search, my predictions were reasonable, but recently things have taken a turn (see the graph) that defies prediction using simple regressions and past history. My last prediction was way off!

I am getting out of the time prediction business. So we will end with a linear graph and a gratuitous cubic below. Useful future predictions should be based not only on heuristics such as found on the pageWhere is the Next Mersenne?, but should also track the usage data for projects like GIMPS. It is the current participants, not the past, which will find the next prime.