A search for ten consecutive primes in arithmetic progression

*** NEWSLETTER/3 ***

*** 7 March 1998 ***

*** THE OFFICIAL ANNOUNCEMENT ***

TEN CONSECUTIVE PRIMES IN ARITHMETIC PROGRESSION

Harvey Dubner, Tony Forbes, Nik Lygeros, Michel Mizony and Paul Zimmermann

In November 1997, having just been successful with eight primes [1], we began a search for nine consecutive primes in arithmetic progression, obtaining help from about a hundred people using a variety of PC's and workstations. On 15 January 1998, one of our PC helpers, Manfred Toplic of Klagenfurt, Austria, found nine consecutive primes in arithmetic progression and a few days later we announced the result on the Internet [2].

At the same time we initiated a search for ten primes. As with nine, we were looking for primes of the form

N*m + x + 210*b, b = 0, 1, ..., 9,

where m = 2*3*5*7*...*193, the product of the first 44 primes, x = 54 53824 16838 87582 66818 97035 90110 65905 78659 34764 60487 38407 81923 51342 11034 95579 and N = 0, 1, 2, .... The 77-digit number x, determined (modulo m) by Nik Lygeros and Michel Mizony using an idea of Harry Nelson (see Dubner and Nelson [3]), was chosen to force

(1) all ten numbers N*m + x + 210*b, b = 0, 1, ..., 9, to be not divisible by primes 2, 3, 5, 7, ..., 193

(2) as many as possible from the 9*209 intermediate numbers to be composite.

Many of the people who helped with nine primes joined us and straight away we began handing out ranges to test. We estimated that 3000 trillion numbers (N's) would need to be sieved for a reasonable chance of success. At 1200 million per hour for a typical Pentium 120, we anticipated about 300 years work spread over perhaps as much as eighteen months of elapsed time.

We were very surprised therefore when on 2 March 1998, Manfred Toplic (yes, the same!) informed us that with Tony Forbes's program, CP10, he had found ten consecutive primes in arithmetic progression. What incredible luck!

The value of N found by Manfred is 507618446770482, corresponding to the ten consecutive primes

P, P+210, P+420, P+630, P+840, P+1050, P+1260, P+1470, P+1680 and P+1890,

where P = 507618446770482*m + x, the first of the sequence, is the 93-digit number

100 99697 24697 14247 63778 66555 87969 84032 95093 24689 19004 18036 03417 75890 43417 03348 88215 90672 29719.

The ten primes were proved by the Jacobi sum test of Adleman, Pomerance, Rumely, Cohen and Lenstra (APRT-CLE in UBASIC) and we would like to thank Francois Morain for providing an independent verification with his elliptic curve program, ECPP.

We got help from about 70 people who searched an estimated total of 48 ranges of a trillion numbers each. Searchers using workstation/Unix and PC/Linux systems ran Paul Zimmermann's program. Thanks to Torbjorn Granlund for making available the fast and efficient GMP library on which that program is based. PC/Windows helpers used Tony Forbes's program, written in C / assembler and incorporating his own multi-precision arithmetic routines.

Along the way, Robert Piche found a new set of nine consecutive primes in arithmetic progression, with N = 580596232159174. This is only the second known example (excluding the two contained in the ten); the other is Manfred's first discovery.

Ben Kibel, Tony Forbes, Rick Heylen, Luke Welsh, Jose-Juan Toharia Zapata, Cyril Banderier and Robert Erra found new sets of eight consecutive primes.

Nigel Backhouse, Robert Piche and Manfred Toplic (again!) found further examples of ten primes in arithmetic progression but in each case the primes were not all consecutive. We expected 100 of these for every one with ten consecutive primes. Hence we finished about 97 percent ahead of schedule!

As you can imagine, we are delighted with the result and so too is Manfred Toplic who could not believe his luck when he discovered that he had broken his own short-lived record of nine consecutive primes. Manfred, 38, who works as a computer operator for a central bank is a keen amateur number theorist. He participates in GIMPS, the 'Great Internet Mersenne Prime Search' and came to our 'consecutive primes' project via George Woltman's page at http://www.mersenne.org.

Although a number of people have pointed out to us that 10 + 1 = 11, we believe that a search for an arithmetic progression of eleven consecutive primes is far too difficult. The minimum gap between the primes is 2310 instead of 210 and the numbers involved in an optimal search would have hundreds of digits. We need a new idea, or a trillion-fold increase in computer speeds. So we expect the Ten Primes record to stand for a long time to come.

Finally, we would like to thank individually the people throughout the world who helped us by using their computers to search one or more ranges. We give the approximate number of ranges in parentheses; for example, (1.5) means 1.5 trillion numbers tested:

Nik Lygeros and Michel Mizony (13.0), Robert Piche (6.0), Tony Forbes (5.62), Rick Heylen (4.76), Manfred Toplic (4.25), Jon L. Kierkegaard (3.0), Robert Erra (2.38), John Lygeros (1.5), Jean-Charles Delepine (1.5), Andy Ketner (1.01), Jan Roger Sandbakken (1.0), Michael Taeschner (0.73), Paul Leunissen (0.70), Hubert Fauque (0.68), Jose-Juan Toharia Zapata (0.66), Paul Zimmermann (0.61), Ray Ballinger (0.58), Torstein Helling (0.51) and Dr. Nigel Backhouse (0.50).

Each of the following also tested part of a range:

Frank A. Adrian, Torbjorn Alm, Gregory Angrist, Cyril Aschenbrenner, Cyril Banderier, Richard Belshoff, Eric Berkhout, Rob Bernhard, Olivier Bosser, John Bray, Paul R. Brown, Richard Carlin, J. Kevin Colligan, Pol Cors, Donald La Curan, Harvey Dubner, Pat Dwyer, Timothy Graham, Alain & Herve Groleau, Hali, Greg Hogan, Kari Hyvnen, Stefan Johan Johannesdal, Kris Johnson, Ben Kibel, Geoffrey Kidd, Mr. Dennis S. Kluk, Ilias Kotsireas, Heikki Kultala, Ken Kriesel, Andy Kveps, Gilles Lamiral, Vincent Langlois, Gabor Megyesi, Olathe, Olly, Andrew Palka, Eirik Milch Pedersen, Richard Pinch, Thomas Pnisch, Steven M. Pretti, Antti Rasinen, Lasse Rasinen, Matthieu Richard Jens Richter, Steve Sadoway, Nicolas Serre, Francoise Spagnesi, Paul Jan Szeptycki, Tanative4, Paul Thomas, Cadet Lawrence D. Turner, Antonio Valdes, Joe W. W., Luke Welsh and Adam G. Weyhaupt.