Printer Friendly

Priming for a lucky strike.

Priming for a lucky strike

Mersenne primes hold a special place in the never-ending pursuit of larger and larger prime numbers-numbers divisible only by themselves and 1. Expressed in the form 2p-1, where the exponent p itself is a prime number, Mersenne numbers have a structure that makes it relatively easy to check whether even enormous numbers truly can't be factored. The largest prime yet found-the 30th Mersenne prime-has 65,050 digits when p=216,091 (SN:9/28/85, p.199).

This week, two computer experts found the 31st Mersenne prime. But to their surprise, the newly discovered prime number falls between two previously known Mersenne primes. It occurs when p=110,503, making it the third-largest Mersenne prime known.

"To tell the truth," says Walter N. Colquitt of the Houston Area Research Center in The Woodlands, TEx., "I didn't expect to find anything." Colquitt, working with computer consultant Luther Welsh Jr. of El Toro, Calif., had written a computer program and organized a systematic search of Mersenne numbers in the hope of finding a record-breaking prime.

This time, because he had only a limited amount of time available on an NEC SX-2 supercomputer, Colquitt decided to run some smaller candidates to be sure that nothing had been missed in previous searches. Only Mersenne numbers with exponents up to 103,000 had been exhaustively searched in the past, says Colquitt. Later efforts had been "shotgun" affairs that covered only narrow ranges of large numbers. The new Mersenne prime falls within one of the gaps.

The supercomputer, running a program written completely in FORTRAN, took only about 11 minutes to confirm that 2110,503-1 is a prime number. "That's an incredibly fast time," says David Slowinski, formerly with Cray Research, Inc., in Minneapolis and now a student at Carnegie-Mellon University in Pittsburgh. "They (must) have some very good trick to get such a fast time." Slowinski himself has discovered several Mersenne primes and plans to check Colquitt and Welsh's result.

"We tried different multiplication algorithms," says Welsh. "The program, as it stands now, is fairly decent, although it's not as fast as it could be."

"If you're going to look for prime numbers," says Colquitt, "you're probably going to learn more about multiplication than you want to know. You also have to be systematic-and you have to be lucky and pray a little bit."

Are there more Mersenne primes lurking in the gaps? "I have absolutely no idea," says Colquitt. "Thousands of them are untested yet."
COPYRIGHT 1988 Science Service, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 1988, Gale Group. All rights reserved. Gale Group is a Thomson Corporation Company.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:31st Mersenne prime number found
Author:Peterson, I.
Publication:Science News
Date:Feb 6, 1988
Previous Article:FDA to evaluate fat substitute.
Next Article:Good-deed viruses stop mouse diabetes.

Related Articles
Prime time for supercomputers.
Computing a prime champion.
Striking pay dirt in prime-number terrain.
Primality tests: an infinity of exceptions.
Dubner's primes: searching for twin primes and other denizens of the number world.
Zeroing in on an infinite number of primes.
The scarcity of cluster primes.
Owners of home computers join researchers in cracking problems and crunching data.
Searchers capture a champion megaprime. (Science News of the week).
New largest prime discovered.

Terms of use | Copyright © 2017 Farlex, Inc. | Feedback | For webmasters