# Striking pay dirt in prime-number terrain.

Against all odds, scientists using a special computer program to sift through gargantuan whole numbers in search of primes--numbers divisible only by themselves and 1 - ventured into largely unexplored territory to bag a new record. Flushed out after 19 hours of calculation on a Cray-2 supercomputer at AEA Technology's Harwell Laboratory in Harwell, England, the largest prime number yet discovered has 227,832 digits, three times as many as the previous record holder (SN: 9/16/89, p.191).

"It was found by absolutely amazing luck," says computer scientist David Slowinski of Cray Research, Inc., in Chippewa Falls, Wis., who developed the software used in searching for so-called Mersenne primes.

Expressed in the form [2.sup.p]-1, where the exponent p is itself a prime number, Mersenne numbers hold a special place in the never-ending pursuit of larger and larger primes. These particular numbers have special characteristics that make it relatively easy to check whether a candidate is either a prime number or the result of multiplying together several smaller numbers.

With an exponent of 756,839, the new champion holds the distinction of being the 32nd and largest Mersenne prime ever found. However, because no one has yet checked all Mersenne numbers having 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 216,091.

Indeed, the latest effort was entirely a shot in the dark. Checking for Mersenne primes provides a convenient test of how reliably a computer functions. When scientists at Harwell requested some numbers to try out while testing their machine, Slowinski provided a list of 100 candidates, selected arbitrarily from about 30,000 possibilities having exponents between 500,000 and 1 million. Incredibly, the Harwell scientists found a prime on their 85th try.

The discovery of such a large Mersenne prime by a hit-or-miss approach actually has little value for computational number theorists interested in the distribution of prime numbers and related mathematical issues. These mathematicians would prefer a more systematic attack that fills in all the gaps.

"It's more fun to go for the record," Slowinski admits. "We're interested in the big ones. We're more like boy scouts looking in the woods at night by flashlight than an organized sheriff's posse."

To fill in the gaps, several computer scientists have banded together to develop improved computer programs for identifying additional Mersenne primes. Calling themselves the "Gang-of-Eight," these researchers have combined ideas from the fields of number theory and signal processing to create a remarkably efficient means of finding and verifying Mersenne primes.

"We've checked exponents from 524,287 down to 430,000 and found no primes," says Richard E. Crandall, chief scientist at NeXT Computer, Inc., in Redwood City, Calif., who participated in verifying the new record.

In an earlier effort, Walter N. Colquitt of the Houston Area Research Center in The Woodlands, Texas, used nearly 8,000 hours of computer time to go as high as 355,031 from his starting point at 216,092. In 1988, he and a colleague had discovered a previously overlooked Mersenne prime with an exponent between 100,000 and 130,000 (SN: 2/6/88, p.85).

"There's still a bit of a gap from about 370,000 up to 430,000, and there's an immense gap between 524,000 and 750,000," Crandall says. "Our program can be used to check up to 32 million, but it's a question of computer time. No one wants to give up the Cray time."

"The new record is going to be awful hard to beat," Colquitt adds. "The hardware has to get a lot faster."

Nonetheless, the search continues. "It's really an amusing sidelight or hobby when nothing else is going on," Slowinski confesses. "It's a shame how work interferes with the important things."

"It was found by absolutely amazing luck," says computer scientist David Slowinski of Cray Research, Inc., in Chippewa Falls, Wis., who developed the software used in searching for so-called Mersenne primes.

Expressed in the form [2.sup.p]-1, where the exponent p is itself a prime number, Mersenne numbers hold a special place in the never-ending pursuit of larger and larger primes. These particular numbers have special characteristics that make it relatively easy to check whether a candidate is either a prime number or the result of multiplying together several smaller numbers.

With an exponent of 756,839, the new champion holds the distinction of being the 32nd and largest Mersenne prime ever found. However, because no one has yet checked all Mersenne numbers having 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 216,091.

Indeed, the latest effort was entirely a shot in the dark. Checking for Mersenne primes provides a convenient test of how reliably a computer functions. When scientists at Harwell requested some numbers to try out while testing their machine, Slowinski provided a list of 100 candidates, selected arbitrarily from about 30,000 possibilities having exponents between 500,000 and 1 million. Incredibly, the Harwell scientists found a prime on their 85th try.

The discovery of such a large Mersenne prime by a hit-or-miss approach actually has little value for computational number theorists interested in the distribution of prime numbers and related mathematical issues. These mathematicians would prefer a more systematic attack that fills in all the gaps.

"It's more fun to go for the record," Slowinski admits. "We're interested in the big ones. We're more like boy scouts looking in the woods at night by flashlight than an organized sheriff's posse."

To fill in the gaps, several computer scientists have banded together to develop improved computer programs for identifying additional Mersenne primes. Calling themselves the "Gang-of-Eight," these researchers have combined ideas from the fields of number theory and signal processing to create a remarkably efficient means of finding and verifying Mersenne primes.

"We've checked exponents from 524,287 down to 430,000 and found no primes," says Richard E. Crandall, chief scientist at NeXT Computer, Inc., in Redwood City, Calif., who participated in verifying the new record.

In an earlier effort, Walter N. Colquitt of the Houston Area Research Center in The Woodlands, Texas, used nearly 8,000 hours of computer time to go as high as 355,031 from his starting point at 216,092. In 1988, he and a colleague had discovered a previously overlooked Mersenne prime with an exponent between 100,000 and 130,000 (SN: 2/6/88, p.85).

"There's still a bit of a gap from about 370,000 up to 430,000, and there's an immense gap between 524,000 and 750,000," Crandall says. "Our program can be used to check up to 32 million, but it's a question of computer time. No one wants to give up the Cray time."

"The new record is going to be awful hard to beat," Colquitt adds. "The hardware has to get a lot faster."

Nonetheless, the search continues. "It's really an amusing sidelight or hobby when nothing else is going on," Slowinski confesses. "It's a shame how work interferes with the important things."

Printer friendly Cite/link Email Feedback | |

Author: | Peterson, Ivars |
---|---|

Publication: | Science News |

Date: | Apr 4, 1992 |

Words: | 645 |

Previous Article: | A moisture problem muddles climate work. |

Next Article: | Beta blockers, depression: breaking the link. |

Topics: |