23 primes in arithmetic progression


On July 24th 2004 myself (Markus Frind), Paul Jobling and Paul Underwood discovered the worlds first 23 primes in arithmetic progression. 56,211,383,760,397 +K*44,546,738,095,860 for K =0 to 22.   Paul Underwood's PIII was the lucky finder.  Paul Underwood contributed 4.9 Ghz, Paul Jobling contributed 2.5 Ghz and I contributed 11 Ghz mostly though Plentyoffish Servers.  The application is memory bound so Ghz is not a indication of effort used in the project. 

Before this search started there were 2 known 22 primes in arithmetic progression  ( AP22 ) . 

11,410,337,850,553 + k*20660*23#  [1]
376,859,931,192,959 + k*83146*23#  [2]


The following AP22's were also found as part of the search for an AP23. ( 23# = 223092870 )  

11,430,832,489,277 + k*65971*23#
57,564,516,803,819 + k*172009*23#
61,168,090,488,293 + k*123663*23#
82,343,600,010,653 + k*133371*23#
82,753,769,539,829 +k*33415*23#
94,244,389,707,469 + k*50879*23#
102,458,805,947,077 + k*106082*23#
121,840,659,021,089 + K*150945*23#
128,248,121,159,371 + k*132852*23#
135,038,293,530,389 +k*135398*23#
168,219,776,115,997 + k*99615*23#
219,555,913,683,761 + k*80504*23#
228,635,458,135,837 + k*68018 *23#
239,043,302,770,157 + k*17205*23#
243,543,595,218,431 + k*68449 *23#
379,825,257,999,359 + k*95753*23#
388,518,661,431,227 + k*121347*23#
391,070,459,886,979 + k*53110*23#
497,003,857,949,969 + k*7826*23#
515,629,258,109,087 + k*31432*23#

I started writing the sieve / AP finder program to search for an AP23 finder in early 2002.  At the time all known algorithms could not find an AP23 in a reasonable amount of time I had to come up with a completely new search concept.   Here is how I went about it.

1. Set up the search so that 192 ranges of  (0..2,500,000) *23#+ (SomeConstantNumber + N * 146078888479) could be searched at once.   SomeConstantNumber  is a prime,  and the value of N is anything that makes the statement coprime.  Ie the equation will never generate a factor less then 29.

2. Each 32 ranges are stored in a bitmap consisting of 2,500,000 32 bit integers.  This ends up creating 6 bitmaps

3. The first 3 bitmaps are OR'd together to create a Working bitmap where we hunt for AP's,  The same is done with the last 3 bitmaps.

4. We now create a sieve, and loop through checking for AP23's.   The sieve/looping will automatically guarantee that all potential AP23's have no factors less then 53.

to download the source code, keep in mind you need to write your own PRP function.

to download the program.   The program is run from a dos prompt by typing  ap23hunter  P     where P is a prime number.

I can be emailed at flames@unforgettable.com

[1] A. Moran, P. Pritchard and A. Thyssen. 1993

[2] Markus Frind April 19, 2003