About 2 years ago, Andrew Wiles, a
researcher at Princeton, claims to have proved the Fermat's Last Theorem
(FLT) and later a large gap was found in the proof. (The gap was filled
later at the end of 1994.) At that time, we, the VACETSERS, had debated
on proving the FLT using numerical methods (i.e., using computer to crank
out the solutions to the famous theorem). One of the first steps in numerical
method is to find the prime numbers, and from that, a "fastest prime
number generator" war was waged among us the VACETSERS. The result
of that "war" was that we were able to reduce the time from tens
of seconds to find all the primes below 1 million to less than 1 second
to find all the primes below 10 million. It was an improvement of more
than 100. It was a fun war. (Actually, for me, anything involved with numbers,
especially prime numbers, is fun.)
Shortly after that "fastest
prime number generator" war, Thomas R. Nicely, Professor of Mathematics
at Lynchburg College, Virginia, computed the sums of the reciprocals of
the twin primes (such as 11 and 13), triplets (such as 11, 13, and 17),
and quadruplets (such as 11, 13, 17, and 19) up to a very large upper bound
(about 10 trillion). He discovered during the summer and fall of 1994 that
one of the reciprocals had been calculated incorrectly by a Pentium computer,
although a 486 system gave the correct answer; this led to the publicization
of the hardware divide flaw in the Pentium floating point unit.
Last week, 9/3/96, an other prime
number news surfaced: The largest known prime is found by a SGI/Cray supercomputer
in the process of quality assurance testing on its systems. The new prime
number, 2^1257787-1 (which denotes 2 multiplied by itself 1,257,787 times
minus one) is the 34th Mersenne prime, discovered by David Slowinski and
Paul Gage. It took about 6 hours on a Cray T94 supercomputer to check this
number. For a 90-MHz Pentium, it would take about 60 hours. The previous
largest known Mersenne prime, 2^859433-1, was also discovered by Slowinski
and Gage in 1994.
Before getting too far with the
new discovery, let's review some basic of prime numbers.
What is a prime number? A prime
number is a positive integer that can be divided only by itself and the
number 1. The first few prime numbers are 2, 3, 5, 7, 11...
What is a Mersenne prime? A Mersenne
prime is a prime number that has the form 2^p-1 where p is also a prime.
Ex: 3=2^2-1 and 7=2^3-1 are the first 2 Mersenne primes.
History: Many early mathematicians
felt that the numbers of the form 2^p-1 were prime for all primes p. But,
in 1536, Hudalricus Regius showed that 2^11-1 = 2047 was not prime (it
is 23*89). This meant that 2^p-1 might or maight not be prime. By 1588
Pietro Cataldi had correctly verified that 2^17-1 and 2^19-1 were both
prime.
In 1644, Father Marin Mersenne,
a French monk, stated that the numbers 2^p-1 were prime for p = 2, 3, 5,
7, 13, 17, 19, 31, 67, 127 and 257. Mersenne's conjecture, even though
later proved to be incorrect, got his name attached to these numbers.
It was obvious to Mersenne's peers
that he could not have tested all of these numbers, but they could not
test them either.
Cataldi's prime (p=19) stood to
be the largest known prime for about 2 centuries until Leonhard Euler in
1772 proved that 2^31-1 is prime. (Through out the history, Mersenne primes
were almost always the largest known primes.) This established the record
for another century until 1876, when Edouard Lucas showed that 2^127-1
(which is a 39 digit number) is prime, and that took the record as far
as the age of the electronic computer. Seven years later I.M. Pervushin
showed 2^61-1 was prime, so Mersenne had missed this one. In the early
1900's R.E. Powers showed that Mersenne had also missed the primes 2^89-1
and 2^107-1. Finally, by 1947, Mersenne's range, p < 258, had been completely
checked and it was determined that the correct list is: p = 2, 3, 5, 7,
13, 17, 19, 31, 61, 89, 107 and 127.
In 1952 the Mersenne numbers p =
521, 607, 1279, 2203, and 2281 were proved to be prime by Robinson using
an early computer and the electronic age had begun.
By 1996 a total of 34 Mersenne primes
have been found. The largest and most recent is p = 1,257,787 which has
378,632 decimal digits.
The table of known Mersenne primes
as of September 3, 1996 is shown below.
n p Year Discoverer
-- ------ ---- ----------------------
1 2 - -
2 3 - -
3 5 - -
4 7 - -
5 13 1461 Anonymous
6 17 1588 P. A. Cataldi
7 19 1588 P. A. Cataldi
8 31 1750 L. Euler
9 61 1883 I. M. Pervushin
10 89 1911 R. E. Powers
11 107 1914 R. E. Powers
12 127 1876 E. Lucas
13 521 1952 R. M. Robinson
14 607 1952 R. M. Robinson
15 1279 1952 R. M. Robinson
16 2203 1952 R. M. Robinson
17 2281 1952 R. M. Robinson
18 3217 1957 H. Riesel
19 4253 1961 A. Hurwitz & J. L. Selfridge
20 4423 1961 A. Hurwitz & J. L. Selfridge
21 9689 1963 D. B. Gillies
22 9941 1963 D. B. Gillies
23 11213 1963 D. B. Gillies
24 19937 1971 B. Tuckerman
25 21701 1978 L. C. Noll & L. Nickel
26 23209 1979 L. C. Noll
27 44497 1979 D. Slowinski & H. Nelson
28 86243 1982 D. Slowinski
29 110503 1988 W. N. Colquitt & L. Welsch, Jr.
30 132049 1983 D. Slowinski
31 216091 1985 D. Slowinski
32? 756839 1992 D. Slowinski & P. Gage
33? 859433 1994 D. Slowinski & P. Gage
34? 1257787 1996 D. Slowinski & P. Gage
It is not known if these last three
primes are the 32nd through 34th Mersenne primes as the region between
them and the previous primes has not been completely tested. Notice that
the 29th Mersenne was found while scanning the region between two primes
found five years earlier.
The way to determine if 2^p - 1
is prime, given that p is prime, is to use the Lucas-Lehmer test:
u := 4; for i := 3 to p do u :=
(u^2 - 2) mod (2^p - 1); if u == 0 then 2^p - 1 is prime; else 2^p - 1
is composite;
The theory for this test was initiated
by Lucas in the late 1870's and then made into this simple test about 1930
by Lehmer.
Note that, with the discovery of
the new prime number, a new perfect number can also be generated. A perfect
number is equal to the sum of its factors. For example, 6 is perfect because
its factors 1, 2 and 3, when added together, equal 6; the next is 28 =
1+2+4+7+14. Mathematicians don't know how many perfect numbers exist. They
do know, however, that all even perfect numbers have a direct relationship
to Mersenne primes, P = 2^(p-1)*(2^p-1) where 2^p-1 is a Mersenne prime.
The new Mersenne prime has 378,632 digits and the new even perfect number
generated with the new Mersenne prime is the 34th known perfect number
and has 757,263 digits. It is not known whether or not there is an odd
perfect number, but if there is one then it is a perfect square times an
odd power of a single prime; it is divisible by at least eight primes and
has at least 29 prime factors; and it has at least 300 decimal digits.
Finding the largest prime numbers
does not have to be exclusive right of high-powered supercomputers. A Florida-based
programmer has organized a hunt for the search for Mersenne Primes using
PC. George Woltman, the search organizer, wanted to take advantage of the
fact that PC central processors waste most of their computing power because
they run on idle much of the time. So Woltman wrote a program that uses
PC, when it's not doing anything else, to help find Mersenne primes. Then
he spread the word on the Internet, in part by setting up a special World
Wide Web site, and asked for help. About 400 volunteers from around the
world have signed up, and Woltman is looking for more. If you'd like to
help, you can check out the web at
https://ourworld.compuserve.com/homepages/justforfun/prime.htm.
Below is the list of some of the
web sites containing the related information on the latest Mersenne prime
number.
HAPPY NUMBER CRUNCHING,
EVERYONE.
Vo Ta Duc
[email protected]
For discussion on this column, join [email protected]
Copyright © 1996 by VACETS and Vo Ta Duc
