This time, it’s a great leap forward.
On June 1, a participant in the Great Internet Mersenne Prime Search (GIMPS) discovered the first known prime number with at least 2 million decimal digits—more than twice as many as the previous record holder.
The discoverer was NayanHajratwala, a consultant at PricewaterhouseCoopers in Plymouth, Mich. Using a Pentium-based personal computer and software written by George Woltman of Orlando, Fla., he identified 26,972,593 - 1 as a prime number, evenly divisible only by itself and 1. Its 2,098,960 decimal digits qualify Hajratwala for a $50,000 prize offered by the Electronic Frontier Foundation (EFF) in Palo Alto, Calif., for the first individual or group who discovers a prime number with at least 1 million digits.
The newly discovered number is the 38th known Mersenne prime, named for the French cleric and mathematician Marin Mersenne (1588-1648). Expressed in the form 2p - 1, where the exponent p is itself prime, Mersenne numbers have characteristics that make it relatively easy to determine whether a candidate is prime. For example, written out in binary form, a Mersenne number consists of an unbroken string of 1s—6,972,593 of them in the case of the record holder.
The smallest Mersenne prime is 3 (22 - 1), or in binary digits, 11. After that comes 7 (23 - 1), or 111, then 31 (25 - 1), or 11111.
With an exponent of 6,972,593, the new champion holds the distinction of being the largest Mersenne prime identified so far. However, because no one has yet checked all Mersenne numbers with smaller exponents, mathematicians can’t be sure that no Mersenne primes lurk in the vast expanse between the record holder and the second-place Mersenne prime, which has an exponent of 3,021,377.
Searching for such large primes has entailed a massive group effort, orchestrated by Woltman, who started GIMPS (see Another Record Prime, Dec. 14, 1996), and facilitated by networking software developed by Scott Kurowski of Entropia.com in San Jose, Calif. Kurowski’s PrimeNet server automatically distributes work to and gathers results from thousands of copies of Woltman’s program residing on more than 21,500 computers throughout the world. The program runs whenever its host computer is otherwise idle, during the night or even between mouse clicks.
Woltman’s software, in turn, relies on a computational algorithm invented by Richard E. Crandall of Reed College and Perfectly Scientific, Inc. in Portland, Ore. That algorithm, called the irrational base discrete weighted transform, speeds up certain large multiplication operations. Crandall’s company has produced a poster featuring (in fine print) all 2,098,960 decimal digits of the current record holder.
Anyone can join the great prime hunt. All it takes is a sufficiently powerful personal computer with idle time on its chips. Check out http://www.mersenne.org/prime.htm for details.
Besides the glory of holding a world record (at least for a while), there is now also a financial incentive. The recently instituted EFF prize for finding a prime number with at least 10 million decimal digits is $100,000. The foundation’s hope is that the prize will spur the technology of cooperative computing and encourage Internet users worldwide to join together in solving scientific problems involving massive computation.
"Using current algorithms, this is more than 125 times as difficult as finding a 2-million-digit prime," Kurowski says. "GIMPS and Entropia.com are gearing up for this challenge now."
"It’s like playing the lottery," comments Joe P. Buhler, deputy director of the Mathematical Sciences Research institute in Berkeley, Calif. "If you’re really lucky, you’ll come up with a winner."
Comments are welcome. Please send messages to Ivars Peterson at email@example.com.
Ivars Peterson is the mathematics/computer writer and online editor at Science News (http://www.sciencenews.org). He is the author of The Mathematical Tourist, Islands of Truth, Newton's Clock, Fatal Defect, and The Jungles of Randomness. He and his wife, Nancy Henderson, have just completed Math Trek: Adventures in the MathZone, a book for children of middle-school age to be published in the fall by Wiley.Ivars Peterson is presently serving as journalist in residence at the Mathematical Sciences Research Institute in Berkeley, Calif. (http://www.msri.org/people/members/ivars).
MATHEMUSEMENTS: Look for math-related articles by Ivars Peterson every month in the children's general-interest magazine Muse (http://www.musemag.com) from the publishers of Cricket and Smithsonian magazine.