*** TEN PRIMES ***
*** NEWSLETTER/1 ***
*** 16 February 1998 ***
*** WELCOME ***
Greetings! Thanks to everybody who worked on the Nine Primes
project and for staying with us to search for ten consecutive
primes in arithmetic progression. Welcome to our new members.
We now have 49 searchers, 37 running the PC/Windows program
CP10 and 12 using workstations/Unix. There's a possibility of
getting on Distributed.net. More about that later, as soon as
something definite has been arranged.
Thanks to Ivars Peterson for including us in *Science News*,
where you can see his article at
http://www.sciencenews.org/sn_arc98/2_7_98/mathland.htm
Congratulations to Roland Clarkson, George Woltman, Scott
Kurowski and the multitude of GIMPS on the discovery of their
third Mersenne prime: 2^3021377 - 1. See George Woltman's
http://www.mersenne.org.
for the story, and thanks to George for including a link from
these pages to us in the section 'More Math[s] Projects'.
*** PROGRESS ***
Dr. Nigel Backhouse has discovered our first example of 10
primes in arithmetic progression. The CP10 result line reads
R 10 35082888253650 ap=10 cp=3 [P.P*P*P.P*P.P*P.P.P] ...
indicating that there are primes at 35082888253650*m + x + 210*b,
b = 0, 1, 2, ..., 9, where m = 2*3*5*...*193, the product of the
first 44 primes and x = 54538241683887582668189703590110659057865
934764604873840781923513421103495579. However there are unwanted
primes (indicated by the asterisks) between b = 1 and 2, between
b = 2 and 3, between b = 4 and 5, between b = 6 and 7, so the 10
primes are not consecutive.
And just recently, Manfred Toplic found another:
R 10 503744050724614 ap=10 cp=4 [P.P.P.P*P.P.P*P.P*P] ...
They are the only examples so far. We expect about a hundred for
every one that has consecutive primes. There is still a long way
to go!
Nik and Michel maintain an up to date progress page at
http://www.desargues.univ-lyon1.fr/home/lygeros/prime10.html
*** THE PROGRAMS ***
If you are running on a workstation under Unix (or PC/Linux),
please make sure you are using program primesAP10, version 3.
You get the binaries for primesAP10 from
ftp://ftp.loria.fr/pub/loria/eureca/tmp/10primes
I am spelling this out because there was an error in the link
from my 'Ten Primes' page. Humble apologies. I hope there has
not been too much confusion. You can check that the program
reproduces Backhouse's result by doing
fontenoy% primesAP.i686 35082888000000 1000000 1000000
********** k=10 (hit 4) n=35082888253650 **********
checked 35082888000000 to 35082889000000 (rem. 76) in 2s 1614M/h
PC/Windows searchers should be using version 2.25 of CP10.
I would be interested if anyone has had any success optimizing
the parameters for CP10. The INI files that I send out specify
200,000 sieving primes and 28,000 words for the sieve table.
This seems to be about right on 'classic' Pentiums. However it
is possible that a larger sieve table and more sieving primes
would work well on a Pentium II with 512K of near-chip cache.
CP10 requires a floating point processor to work perfectly.
*** SOME THEORY ***
We seek ten consecutive primes of the form
N*m + x + 210*b, b = 0, 1, 2, ..., 9,
where m = 193#, the product of the primes up to 193, x = 54538
24168388758266818970359011065905786593476460487384078192351342
1103495579, and N = 1, 2, 3, .... The common difference of the
arithmetic progression must be a multiple of 210, so we choose
the smallest, namely 210 itself. Observe also that x == 1
(mod 11) and the 10 elements of the arithmetic progression are
congruent to 1, 2, ..., 10 (mod 11). The parameter x, found by
Nik and Michel, is chosen to force as many as possible of the
remaining 1881 numbers in the interval [N*m + x, N*m + x + 1890]
to be composite.
Both programs use a two stage process. First, we sieve a batch
of N's by primes from p = 197 up to some limit, R. That is, we
start with a range [N_0, N_1] and for each p and for b = 0, 1,
2, ..., 9, we remove all N in [N_0, N_1] which satisfy
N == (-x - 210*b)/m (mod p).
This sieves out N's that generate arithmetic progressions
N*m + x + 210b, b = 0, 1, 2, ..., 9 with at least one member
divisible by a sieving prime. We expect a proportion of about
product{193 < p <= R, p prime: (p - 10)/p}
N's to survive. Typically, CP10 uses 200000 sieving primes,
corresponding to R = 2750773 and a reduction factor of about
28000 to 1.
We check the numbers in the remaining arithmetic progressions
with the fast but not perfect Fermat test: n is probably prime
if 2^n == 2 (mod n). We also need to test the numbers in
between to see if there are any 'unwanted' primes. The choice
of the parameter x attempts to reduce this possibility to the
minimum.
Finally, when we do find ten consecutive (probable) primes in
arithmetic progression, they must be verified as true primes
by the Jacobi sum test of Adleman, Pomerance, Rumely, Cohen
and Lenstra (APRT-CLE in UBASIC), or by Atkin and Morain's
elliptic curve method.
***
Harvey Dubner
Tony Forbes
Nik Lygeros
Michel Mizony
Paul Zimmermann
--
Tony