From tonyforbes@ltkz.demon.co.uk Mon Mar 9 07:10:25 1998
Date: Sun, 8 Mar 1998 13:55:47 -0500
From: Tony Forbes
To: NMBRTHRY@LISTSERV.NODAK.EDU
Subject: Ten Consecutive Primes in Arithmetic Progression
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 92-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), 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),
John Lygeros (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, Robert Piche, Richard Pinch, Matthieu Plasma,
Thomas Pnisch, Steven M. Pretti, Antti Rasinen, Lasse Rasinen,
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.
REFERENCES
[1] Harvey Dubner, Tony Forbes, Nik Lygeros, Michel Mizony
and Paul Zimmermann, '8 consec. primes in AP', NMBRTHRY,
November 1997.
http://listserv.nodak.edu/scripts/wa.exe?A2=ind9711&L=nmbrthry&O=T&P
=209
[2] Harvey Dubner, Tony Forbes, Nik Lygeros, Michel Mizony
and Paul Zimmermann, '9 consecutive primes in arithmetic
progression', NMBRTHRY, January 1998.
http://listserv.nodak.edu/scripts/wa.exe?A2=ind9801&L=nmbrthry&O=T&P
=982
[3] Harvey Dubner and Harry Nelson, 'Seven consecutive
primes in arithmetic progression,' Math. Comp.,
Volume 60, Number 220, October 1997, pp 1743-1749.
E-MAIL ADDRESSES
Harvey Dubner
Tony Forbes
Michel Mizony
Nik Lygeros
Paul Zimmermann
Manfred Toplic
--
Tony