Problems & Puzzles: Puzzles

Puzzle 6.- Ray Ballinger suggestion

Ray Ballinger notes that for the prime numbers of the form k*2^n+1, k=12909 is a very productive coefficient since he and Wilfred Keller have detected 73 primes with 73 distinct n values. He notes also that for primes of the form k*2^n-1, k=81555 is the most productive coefficient. 

Ray Ballinger suggests to keep tracking this kind of coefficients (and - of course - the exponents that makes N a prime number! ) 

Then I offer this page to maintain these records. 

k Primes(P) n max 
Index = 
2863575 81 53656 
7.437 Brennen
12909 81 53118 
7.444 Ballinger & Keller
28995 90 28108 
8.785 Keller
577294575 113 33772 
10.836 Brennen (6/9/1998)
945561887392230553579269135 142 109667
  Smith, Carmody (8/2/03). See below.


k Primes(P) n max 
Index = 
81555 66 24351 
6.543 Ballinger & Keller
22932195 92 25038 
9.083 Jack Brennen (6/9/1998)
147829610027385 97 21493 9.7238 Robert Smith (19/11/2002)

** [n] means  limit of known search 
***if you want the exponents n, I can sent them by mail  

And, naturally I continue asking  for the following more productive k coefficients.


Robert Smith wrote (19/11/2002):

I finally cracked, using pfgw, the record for the k*2^n-1 series, after 10 months!

And the k is 147829610027385, which has produced 97 primes in the first 21493 n values, which is, I think 9.7238 on your measure. I really enjoyed this one. Now I am going to spend a lot shorter time looking for the + series record.

The choice of k is not too random. It is a result of searching for the most efficient k values in terms of prime production. See more at


The 8/2/2003, Robert Smith wrote:

"... please find below a candidate (k=945561887392230553579269135) with 142 primes (k*2^n+1) in less than 110000n.

Thanks to Phil Carmody's fantastic k sieving capability, he was able to generate in excess of 50,000 Payam number candidates, all of which are hugely prime up to n=100, for further exploration by me. There was so much work to do here to eliminate the merely hugely prime series from the incredibly prime - superlatives fail me here. The side benefit of the work is that there are about 10 other candidate k which will also break Jack's record, if you believe in statistical certainties.

I would be grateful if you would credit myself and Phil Carmody equally for this discovery, along with NewPGen 2.80 for the n sieve and pfgw for the prime proving."


Phil Carmody wrote (5/5/03):

Recently I've been looking at what I call "Proth Racing", which is basically what your puzzle 6 is about (you may hae noticed my involvement with Robert Smith on this puzzle). I've decided to put together a website about my prime drag racing exploits, which will include some new records.

I've only written a tiny fraction of the pages so far, but there's a skeleton there already.

Anyway, as a taster for the records that are going to be on those pages, here are some new records for the k*2^n-1 table. The first is the number which achieves an index of 10 most quickly, and also the largest number of primes up to n=1000. The second is the fastest number to find 100 primes.

k, P, n, index
15865502462238176449845, 69, 989, 10.0047931200345
16754719175394037218524715, 100, 5968, 11.5019642903179

Note that the current record for the k*2^n+1 form is equally out of date, Robert and I have some amazing new numbers in the last few months. Robert will announce those some time soon.


 Thomas Ritschel wrote (August 2012)

Quite a while a ago I joined Robert Smith's search for Very Prime Sequences
(see: ).
I concentrated on the Sierpinski side, e.g. numbers of the the type k*2^n+1.

After finding a sequence of 172 primes (at n=350000) in 2010
(see: I was trying to improve this record a little further.
Thanks to an improved preselection software written by Robert Gerbicz I was able to scan a wide range of k, resulting in a bunch of more than 15000 k's, each yielding 100+ PRPs at n=10000.

Finally, after more than two years, I found a nice pair of record breakers, yielding 177 and 180 primes up to n=340000:

The first k is 30562993973479965532402725 which produces 180 primes up to n=338615, P/ln(n)=14.137.
The second k is 32268186233370440249391495 which produces 177 primes up to n=323172, P/ln(n)=13.952.

And there is another noteworthy k which yields 120 primes until n=10000:
k=29625624785566557571174065 with the 120th prime at n=9805, P/ln(n)=13.057.

Note that Robert Smith also produced quite a few new numbers for the "minus side", so that the record for the k*2^n-1 form is also out of date.


Robert Smith wrote on August 5, 2013:

Please see the link below that announces a k with 204 primes to date. I found  the k, but the workload for prime finding, especially for higher n, was shared between myself and Thomas Ritschel.
I personally think that beating this candidate will require a lot of computing power!




Records   |  Conjectures  |  Problems  |  Puzzles