Supercomputer Comes Up With Whopping Prime Number

Computer scientists have accidentally stumbled on the largest prime number ever discovered. It is the number 2 raised to the 216,091st power minus 1, which contains 65,050 digits and would fill two pages if printed in this newspaper.

Prime numbers are numbers that have no divisors other than themselves and 1. For example, 13 is prime, but 14, which is the product of 2 and 7, is not. The ancient Greeks knew that there are an infinite number of primes, but no one has ever come up with a formula for generating them.

While there is no known practical use for 65,000-digit prime numbers, the method that finds them requires trillions of calculations and is therefore a useful test of the reliability of large supercomputers. It has also engendered an informal competition among supercomputer manufacturers for recognition as the fastest machines on the market. The faster a computer is, the larger the numbers it can test.

The latest prime was discovered within the last few weeks on a Cray X-MP supercomputer that was being tested by Chevron Geosciences Co. in Houston. The machine, which costs more than $10 million, was recently delivered to Chevron, which plans to use it to analyze geological data in exploring for oil.

To test the machine, computer scientists at Chevron, under the direction of Vice President William Bartz, ran a special program that checks large numbers to determine if they are so-called Mersenne primes. The number they discovered by chance is the 30th Mersenne prime discovered. It took more than three hours to test the number on a machine that does 400 million calculations a second.

Mersenne primes were named for Marin Mersenne, a 17th-Century French monk who investigated them. They take the form 2 raised to a prime power minus 1. The first three Mersenne primes are 3 (2 to the 2nd power minus 1), 7 (2 to the 3rd power minus 1) and 31 (2 to the 5th power minus 1).

“We just happened to crunch enough numbers to come up with a new prime,” Bartz said Monday from Houston. “It’s my responsibility to get the machine up and running and make sure we have a good one and not a lemon. The results are interesting, if true, but they are certainly not going to help me find oil.”

Because of their special form, there is a test that can be applied to very large numbers to determine whether they are Mersenne primes. Numbers that have no special form cannot be tested for primality if they are larger than 100 digits or so. The brute-force method of primality testing--attempting to divide the number by all possible factors--is too time-consuming, even for the fastest machines.

The previous largest Mersenne prime, the 29th, was 2 to the 132,049th power minus 1, a number with 39,751 digits. It was found in 1983 by David Slowinski of Cray Research Inc. in Chippewa Falls, Wis.

Because the testing of possible Mersenne primes is not being done systematically, there is no guarantee that all of the numbers between 132,049 and 216,091 have been checked. It is possible that there are other Mersenne primes lurking in between. People who want to test a new computer or who have free time--even free seconds--on a supercomputer take a stab at a region they think may be promising.

“Anyone who is doing it is doing it for his own amusement,” said Slowinski, who wrote the program that ran at Chevron and came up with the new Mersenne prime. “It’s not a coordinated effort like a steam engine pulling a train up a mountain. It’s more like dozens of little rowboats on a lake.”

“It’s a learning experience, and it’s a challenge,” said Steve McGrogan of Elxsi computers in San Jose, who doubled-checked the Houston work. “It’s like Mt. Everest. Why do people climb mountains?”