*** 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<hdubner1@compuserve.com>
Tony Forbes<tonyforbes@ltkz.demon.co.uk>
Nik Lygeros<lygeros@desargues.univ-lyon1.fr>
Michel Mizony<mizony@desargues.univ-lyon1.fr>
Paul Zimmermann<paul.zimmermann@loria.fr>

Prepared by Tony Forbes