Ivars Peterson's MathTrek

November 17, 1997

# A Progression of Primes

Searches for patterns among prime numbers -- whole numbers exactly divisible only by themselves and one -- have long served as stiff tests of the ingenuity and perseverance of mathematicians. In recent years, the use of computers has brought a steady stream of record-breaking results.

In 1995, Harvey Dubner, a semiretired electrical engineer in New Jersey, and Harry L. Nelson, retired from the Lawrence Livermore (Calif.) National Laboratory, announced that they had found seven consecutive primes in arithmetic progression, establishing a new record.

In other words, Dubner and Nelson had unearthed a sequence of seven prime numbers in which each successive number is 210 larger than its predecessor, starting with the following 97-digit prime: 1,089,533,431,247,059,310,875,780,378,922,957,732,908,036,492,993,138,195,385,213,105,561,742,150,447,308,967,213,141,717,486,151.

Nelson had gotten the idea of looking for such a string of consecutive primes after reading about these sequences in Paulo Ribenboim's The Book of Prime Number Records. In general, an arithmetic progression consists of a set of integers a, a + d, a + 2d, a + 3d, and so on, where a is greater than 0 and d is greater than or equal to 2.

The longest known string of primes in arithmetic progression contains 22 terms. The smallest prime in the sequence is 11,410,337,850,553 and the difference, d, is 4,609,098,694,200. It was found in 1993 and required the use of more than 60 computers.

Nelson was after something a little more specific: seven consecutive primes with a difference equal to 210, which is the smallest possible difference. He suggested the problem to Dubner, who had several personal computers specially modified and programmed to handle computations involving prime numbers. They reasoned that numbers 90 to 100 digits long would be a good place to search for the required sequence.

Initially, Dubner thought that the computations would take too long to be practical, but Nelson introduced a mathematical shortcut -- a way of eliminating a large proportion of the candidate numbers -- that considerably reduced the computation time needed for the search.

Dubner ended up using seven computers, running continuously for about 2 weeks, to find the sequence.

About 2 months ago, Paul zimmermann of INRIA Lorraine in France asked Dubner whether the method used to find the seven-prime sequence could be applied when the primes fall within a specified range of numbers. The answer was yes, and zimmermann promptly wrote a computer program that ran considerably faster than Dubner's version.

"Suddenly, finding eight primes became a good possibility," Dubner says. Dubner then got help from Tony Forbes in Great Britain, who made further improvements to speed up the search program.

Dubner, zimmermann, and Forbes, together with Nik Lygeros and Michel Mizony of Claude Bernard University in Lyon, used about a dozen computers to search for eight consecutive primes in arithmetic progression. One of zimmermann's computers found the sequence on Nov. 3, setting the new record.

The starting prime is 43,804,034,644,029,893,325,717,710,709,965,599,930,101,479,007,432,825,862,362,446,333,961,919,524,977,985,103,251,510,661, with each successive prime 210 larger.

Dubner, zimmermann, and Forbes are now looking for help to find a sequence of nine consecutive primes in arithmetic progression. "We estimate that this will take . . . 6,000 computer-days," Dubner says. "We would like to have about 200 computers running so that finding nine primes will take about a month."

References:

Dubner, Harvey, and Harry Nelson. 1997. Seven consecutive primes in arithmetic progression. Mathematics of Computation 66:1743-1749.

Guy, Richard K. 1994. Unsolved Problems in Number Theory. New York: Springer-Verlag.

Peterson, Ivars. 1995. Progressing to a set of consecutive primes. Science News 148(Sept. 9):167.

______. 1993. Dubner's primes. Science News 144(Nov. 20):331.

Ribenboim, Paulo. 1996. The New Book of Prime Number Records. New York: Springer-Verlag.