*** SEARCH FOR NINE CONSECUTIVE PRIMES IN ARITHMETIC PROGRESSION ***
*** NEWSLETTER/3 ***
6 December 1997
Hello once again.
*** PROGRESS ***
Thanks to everybody for reporting your results.
We now have 26 "near misses" (9 primes in A.P.):
Bruce Biavatti
R 9 418190976673878 ap=9 cp=5 [-1:C*P.P.P.P.P*P*P.P.P*C:+9]
Stan Cohen
R 9 409107650676672 ap=9 cp=5 [-1:C.P.P.P.P.P*P.P*P*P*C:+9]
R 9 409128886042763 ap=9 cp=4 [-1:C*P.P.P.P*P.P.P*P*P*C:+9]
Harvey Dubner
R 9 400000508797243 ap=9 cp=5 [-1:C*P*P.P.P.P.P*P.P.P*C:+9]
R 9 402224283386010 ap=9 cp=5 [-1:C.P.P.P.P.P*P.P*P*P.C:+9]
Hubert Fauque
R 9 415050637639089 ap=9 cp=4 [-1:C*P*P.P.P.P*P.P.P.P*C*+9]
Tony Forbes
R 9 302582092752805 ap=9 cp=3 [-1:C.P*P*P.P*P.P.P*P.P*C:+9]
R 9 302692436524493 ap=9 cp=4 [-1:C*P.P.P.P*P.P*P.P.P.C:+9]
Becky & Greg Jaxon
R 9 328069176725833 ap=9 cp=5 [-1:C*P.P*P*P*P.P.P.P.P*C*+9]
Torsten Metzner
R 9 226139828468252 ap=9 cp=5 [-1:C.P*P.P*P*P.P.P.P.P*C:+9]
Michel Mizony and Nik Lygeros
R 9 238560839501648 ap=9 cp=2 [-1:C*P*P.P*P.P*P.P*P*P.C:+9]
Paul Nicholson
R 9 229588936903020 ap=9 cp=3 [-1:C*P.P.P*P.P.P*P*P.P*C:+9]
R 9 240056180976390 ap=9 cp=2 [-1:C*P.P*P*P.P*P*P*P*P*C:+9]
R 9 240614403401390 ap=9 cp=5 [-1:C*P*P*P*P*P.P.P.P.P*C:+9]
Michel Quercia
R 9 233009952168708 ap=9 cp=5 [-1:C.P.P.P.P.P*P*P*P*P*C:+9]
R 9 233319609748154 ap=9 cp=4 [-1:C*P.P.P.P*P*P.P.P*P*C:+9]
R 9 233571893912031 ap=9 cp=2 [-1:C*P.P*P.P*P*P.P*P.P.C:+9]
R 9 241383633852070 ap=9 cp=4 [-1:C*P.P.P*P.P.P.P*P*P*C:+9]
R 9 241956398131452 ap=9 cp=4 [-1:C.P*P*P*P.P.P.P*P.P*C:+9]
R 9 244034072310109 ap=9 cp=4 [-1:C.P.P.P.P*P.P*P*P*P*C:+9]
Gerald Ruescher
R 9 305108859507098 ap=9 cp=4 [-1:C*P.P.P*P.P.P.P*P*P*C:+9]
R 9 305307938469663 ap=9 cp=5 [-1:C.P*P.P.P.P.P*P.P*P*C:+9]
Stefan Wehmeier
R 9 242650800387366 ap=9 cp=7 [-1:C*P*P*P.P.P.P.P.P.P*C:+9]
R 9 242695575523580 ap=9 cp=8 [-1:C*P.P.P.P.P.P.P.P*P*C:+9]
Paul Zimmermann
R 9 220214727578475 ap=9 cp=4 [-1:C.P.P.P.P*P*P.P*P.P.C:+9]
R 9 221153832755059 ap=9 cp=7 [-1:C*P.P.P.P.P.P.P*P*P*C:+9]
And a number of "near hits" (8 consecutive primes in A.P.):
Harvey Dubner
R 8 400088345825136 ap=8 cp=8 [-1:C.C.P.P.P.P.P.P.P.P.C:+9]
Robert Dubner (Harvey's son)
R 8 404323275143576 ap=8 cp=8 [-1:C*C.P.P.P.P.P.P.P.P*C:+9]
Hubert Fauque
R 8 415357208288569 ap=8 cp=8 [-1:C*P.P.P.P.P.P.P.P*C*C:+9]
Tony Forbes
R 8 303360676324814 ap=8 cp=8 [-1:C.C*P.P.P.P.P.P.P.P*C:+9]
Michel Mizony and Nik Lygeros
R 8 220458527093293 ap=8 cp=8 [-1:C*P.P.P.P.P.P.P.P*C*C:+9]
R 8 238613448197617 ap=8 cp=8 [-1:C.P.P.P.P.P.P.P.P.C.C:+9]
R 8 238913241290933 ap=8 cp=8 [-1:C*P.P.P.P.P.P.P.P.C.C:+9]
Craig Stevenson
R 8 321173808733695 ap=8 cp=8 [-1:C*C.P.P.P.P.P.P.P.P*C:+9]
Sturle Sunde
R 8 228862441305057 ap=8 cp=8 [-1:C*P.P.P.P.P.P.P.P.C.C:+9]
Stefan Wehmeier
R 9 242695575523580 ap=9 cp=8 [-1:C*P.P.P.P.P.P.P.P*P*C:+9]
(also a near miss)
Paul Zimmermann
R 8 221236230528997 ap=8 cp=8 [-1:C*P.P.P.P.P.P.P.P.C.C*+9]
R 8 220237184434352 ap=8 cp=8 [-1:C.P.P.P.P.P.P.P.P.C*C:+9]
More details can be found at
http://www.loria.fr/~zimmerma/records/progress.html
*** REPORTING INTERESTING RESULTS ***
I will try and clarify what to report. We are interested
immediately in any example of 9 primes and any example of 8
*consecutive* primes in arithmetic progression.
If you are running CP09, all you need do is keep an eye on the
three numbers 'hit9', 'near9' and 'hit8' and see if any of
them change. Then search the DAT file with NOTEPAD or your
favourite editor (NOTEPAD lets you do this on the fly, without
stopping the program). Look for lines beginning 'R 9' or any
lines beginning 'R 8' and containing 'cp=8'. Cut and paste
them into an email to whichever of us you are registered with.
(Or just send your entire DAT file.)
Paul Zimmermann also collects every occurrence of seven
*consecutive* primes in arithmetic progression ('R 8' or
'R 7' with 'cp=7'). If you get any of these in the DAT file,
you can extract and mail them to him.
If you are running the Unix program, please report 9 primes
in A.P. and 8 or 7 *consecutive* primes in A.P. You can
search for them easily in the log file with the 'grep'
command:
% grep 'k=9' log; grep 'k=8 (hit 0)' log; grep 'k=7 (hit 0)' log
*** NEW VERSION OF THE WINDOWS PROGRAM ***
Version 2.20 of CP09 is now ready to download from
http://www.ltkz.demon.co.uk/ar2/cp09v220.zip
It is much faster than 2.19. Expect about a billion per hour
with a Pentium 120, and some computers could see an amazing
improvement of around 50 percent.
*Note well* that you must reduce the 5th INI parameter, sv_K
(size of the sieve table), to about 28000. This is the value
in the current CP09TEST.INI. If you leave it at 100000, you
may not see any benefit.
The main change is that the sieve now uses a single table of
bits instead of 32 parallel tables of words. The latter worked
well and was clearly superior when I was looking for 16- and
17-tuples of primes, where the sieving primes are quite small.
However, and I have always had a nagging doubt about this,
when you have to sieve with large primes, the overheads of
setting up 32 small sieves exceed the benefits of using word-
based tables. Curiously, the effect is not noticeable with a
table of 100000 words, but the improvement is dramatic when
it is reduced in size to 28000 words.
The other change you will notice is that CP09 now writes to
the screen after every five batches. On a typical 486/66 this
means about once a minute.
The ZIP file includes a 'no yields' version for W95 and NT
users to experiment with.
*** SOME THEORY ***
We seek nine consecutive primes in arithmetical progression,
Z, Z+210, Z+420, ..., Z+1680.
If you have 9 primes in arithmetic progression Z, Z+d, Z+2*d,
Z+3*d, ..., Z+8*d, and Z is greater than 7, then d must be
divisible by the primes 2, 3, 5 and 7, and hence by 210. For
example, if d is not divisible by 5, then one of Z, Z+d,
Z+2*d, Z+3*d or Z+4*d will be divisible by 5.
Given that the difference must be a multiple of 210 and that
the numbers should be as small as possible, it is right to
fix the difference at 210. Then it makes sense to look for
primes in a region where the expected density of the primes
is about one every 210. Using the prime number theorem as a
guide, this suggests we look in the region where ln(Z) = 210,
or exp(210) = 1.6*10^91.
(This is no longer true for 11 primes. The simplistic argument
above would tell us to search for number of about 1000 digits,
but the optimum is nearer 700 digits. To do the job properly
we have to take into account the cost of the primality tests.)
The next step is to choose suitable Z's. Using methods of
Dubner and Nelson, Paul Zimmermann has determined two
parameters Q and H_0, Q = 193# = product of the primes 2, 3,
5, 7, ..., 193 and H_0 =
H_0 = 6240141611007307622465889025426185177074468140120944390_
087327315890659848721
which determine the Z's,
Z = N*Q + H_0
where N is in the range 200*10^12 to about 500*10^12. With
these parameters, it turns out that all except 85 the
intervening numbers are forced to be composite for all N.
The sieving part of the program eliminates N for which one of
N*Q+H_0+210*b, b = 0, 1, ..., 8 is divisible by a prime
between 197 and some upper limit, typically about 4 million.
For N's that survive the sieve, N*Q+H_0+210*b are tested for
probable primality using the simple Fermat test: x is probably
prime if 2^x == 2 (mod x). Sets of numbers that pass this
test are analysed further to see if all the intervening
numbers are composite. Finally, the primes must be verified
by, for example, the Jacobi sum method of Adleman, Pomerance,
Rumely, Cohen and Lenstra (APRT-CLE in UBASIC), or the
elliptic curve proof of Atkin and Morain.
An excellent Web site for primes is Chris Caldwell's
http://www.utm.edu/research/primes/largest.html
For primes in arithmetic progression, the only sites I know
of are Paul's and mine,
http://www.loria.fr/~zimmerma/records/9primes.html
http://www.ltkz.demon.co.uk/ar2/9primes.htm
A useful book is Richard K. Guy, *Unsolved Problems in Number
Theory*, Springer Verlag, New York, 1994.
*** CALCULATION OF EXPECTED SEARCH EFFORT ***
This is a somewhat simplified approach to calculating various
values that can be used for timing estimates. Let
Z = N*m + x,
m = 193# = 2*3*5*7*11*...*193,
x = 62401416110073076224658890254261851770744681_
40120944390087327315890659848721
For a typical Z of around 10^92,
Prob(a Z is prime): exp(0.5772)*ln(193)/ln(Z) = 1/22.6,
Prob(9 Z's are prime): 1/(22.6)^9 = 1/(1.54*10^12).
Thus 1.54 trillion values of N are checked on average to find
Z such that the nine numbers Z, Z+210, Z+420, ..., Z+1680 are
all prime (a hit or near miss).
The parameter x ensures that all except possibly 85 of the
remaining numbers between Z and Z+1680 are composite. Hence
we multiply the above probability by
Prob(85 remaining composites): = (1 - 1/22.6)^85 = 1/46.8.
Thus on average 46.8*1.54*10^12 = 72 trillion N's are examined
to get nine consecutive prime Z's (a hit).
Put another way, in a trillion numbers, one can expect about
0.014 hits and about 0.65 near misses. At a billion numbers
per hour, the total search effort would be about 3000 days.
*** TEN PRIMES ?? ***
Paul Zimmermann estimates that we need to sieve about 2600
trillion N's to have a reasonable chance of finding ten
consecutive primes in arithmetical progression. Assuming a
rate of 1200 million per hour, that's nearly 250 computer-
years, about 8 years of real time with the current helpers,
instead of the expected 2 months.
***
Best wishes and happy searching,
Harvey Dubner <70372.1170@compuserve.com>
Tony Forbes
Nik Lygeros
Michel Mizony
Paul Zimmermann