*** 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