History of Mathematics Project | SWAC Computes New Mersenne Primes

History of
Mathematics

Project

1952

SWAC Computes New Mersenne Primes

Five new Mersenne primes

An early electronic computer called the SWAC was used to find the five largest prime numbers known as of 1950.

The SWAC (an acronym for Standards Western Automatic Computer) was an early electronic digital computer built in 1950 by the U.S. National Bureau of Standards (the previous name for the present National Institute of Standards and Technology) in Los Angeles. At the time of its completion in August 1950, it was the fastest computer in the world. In January 1952, mathematician Raphael Robinson used the SWAC to discover five new Mersenne primes, i.e. prime numbers of the form 2^n–1, with n = 521, 607, 1279, 2203 and 2281. Upon their discovery, these numbers were the largest known prime numbers, having 157, 183, 386, 664 and 687 digits, respectively. One of the computer's electrostatic memory tubes is preserved and displayed as part of the Computer History Exhibits at the Gates Computer Science building at Stanford University.

Artifact origin

Los Angeles, United States

Timeline

Interactive Content

Computational Explanation

A Mersenne prime is a Mersenne number, i.e. a number of the form



-1

, that is prime. In order for

to be prime, n must itself be prime. However, only a small fraction of Mersenne numbers with prime indices are themselves prime. Mersenne primes were first studied because of their remarkable property that every Mersenne prime corresponds to a perfect number.

It has been conjectured that infinitely many Mersenne primes exist. However, despite the fact that there exists an efficient primality test for them known as the Lucas–Lehmer test, finding Mersenne primes remains computationally very challenging. For this reason, the search for Mersenne primes challenges the limits of computational technology. As of this writing, Mersenne primes make up nine of the 10 largest known primes.

The Lucas–Lehmer test performs repeated modular arithmetic operations. If the last computed value is zero, then the corresponding Mersenne prime is a prime number. This test can be implemented very simply in the Wolfram Language as:

In[]:=

LucasLehmerPrimeQ[p_]:=Nest[Mod[#^2-2,2^p-1]&,4,p-2]0

Applying the test rapidly identifies all Mersenne prime indices in the range 2–1000:

Select[Range[2,1000],LucasLehmerPrimeQ]//Timing

Out[]=

{2.39611,{3,5,7,13,17,19,31,61,89,107,127,521,607}}

Since only prime indices need be considered, the computation can be greatly sped up simply by considering only prime indices:

In[]:=

Select[Prime[Range[PrimePi[1000]]],LucasLehmerPrimeQ]//Timing

Out[]=

{0.378377,{3,5,7,13,17,19,31,61,89,107,127,521,607}}

As of 1951, only 12 Mersenne primes were known, the most recent having been found by E. Lucas in 1876. It was therefore revolutionary that Robinson was able to find not just one but five new Mersenne primes in the year 1952. Here are the indices of the primes found by Robinson:

In[]:=

indices=MersennePrimeExponent[Range[13,17]]

Out[]=

{521,607,1279,2203,2281}

Forming the corresponding Mersenne numbers:

In[]:=

mersennes=2^indices-1;

… and testing confirms their primality:

In[]:=

PrimeQ[mersennes]

Out[]=

{True,True,True,True,True}

These prime numbers range in length from 157 to 687 decimal digits:

In[]:=

IntegerLength[mersennes]

Out[]=

{157,183,386,664,687}

While 687 digits was a lot in 1952, modern digital computers can handle many more. In fact, what took days and months to compute in 1952 can now be computed in seconds, as illustrated by the following Wolfram Language computation, which finds the first 17 Mersenne primes in about 1.5 seconds:

In[]:=

Select[Prime[Range[PrimePi[3000]]],PrimeQ[2^#-1]&]//Timing

Out[]=

{1.55439,{2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281}}

As a result of advances in digital computing, a total of 51 Mersenne primes have been found as of mid-2020. The computation of these huge numbers is done via a distributed computing project known as GIMPS. As of 2020, the largest known prime is the Mersenne number

82589933

-1

, which requires a truly staggering 24,862,048 decimal digits to express.

While 51 Mersenne primes are known, it has not yet been established that no additional Mersenne primes exist between

and

. As a result, it is possible to list definitively only the first 47 Mersenne primes:

TextGridFlatten/@Transpose[Partition[Append[MapIndexed[{#2[[1]],Row[{Superscript[2,#],"-",1}],IntegerLength[2^#-1]}&,MersennePrimeExponent[Range[47]]],{"","",""}],12]],

Rule[

]



Out[]=

1	2 2 -1	1	13	521 2 -1	157	25	21701 2 -1	6533	37	3021377 2 -1	909526
2	3 2 -1	1	14	607 2 -1	183	26	23209 2 -1	6987	38	6972593 2 -1	2098960
3	5 2 -1	2	15	1279 2 -1	386	27	44497 2 -1	13395	39	13466917 2 -1	4053946
4	7 2 -1	3	16	2203 2 -1	664	28	86243 2 -1	25962	40	20996011 2 -1	6320430
5	13 2 -1	4	17	2281 2 -1	687	29	110503 2 -1	33265	41	24036583 2 -1	7235733
6	17 2 -1	6	18	3217 2 -1	969	30	132049 2 -1	39751	42	25964951 2 -1	7816230
7	19 2 -1	6	19	4253 2 -1	1281	31	216091 2 -1	65050	43	30402457 2 -1	9152052
8	31 2 -1	10	20	4423 2 -1	1332	32	756839 2 -1	227832	44	32582657 2 -1	9808358
9	61 2 -1	19	21	9689 2 -1	2917	33	859433 2 -1	258716	45	37156667 2 -1	11185272
10	89 2 -1	27	22	9941 2 -1	2993	34	1257787 2 -1	378632	46	42643801 2 -1	12837064
11	107 2 -1	33	23	11213 2 -1	3376	35	1398269 2 -1	420921	47	43112609 2 -1	12978189
12	127 2 -1	39	24	19937 2 -1	6002	36	2976221 2 -1	895932

Other Resources

Additional Reading

Huskey, H. D. Harry D. Huskey: His Story. BookSurge Publishing, 2004.
Office of Naval Research, Arlington Virginia. Digital Computer Newsletter, Vol. 4, No. 2, p. 3, April 1952.
Rutland, D. Why Computers are Computers: The SWAC and the PC. Wren Publishers, 1995.
Rutland, D. "The SWAC: First Computer on the West Coast." The Analytical Engine, Vol. 4, No. 1, pp. 31–34, 1997.

Additional Links

Image Credits

National Institute of Standards and Technology, Wikimedia

SWAC Computes New Mersenne Primes

Timeline

Interactive Content

Computational Explanation

Other Resources

Wolfram MathWorld

Additional Reading

Additional Links

Image Credits