The Riesel Problem: Definition and Status

Compiled by Wilfrid Keller

In 1956 Hans Riesel proved the following interesting result.

Theorem. There exist infinitely many odd integers k such that k · 2n − 1 is composite for every n > 1.

Actually, Riesel showed that k0 = 509203 has this property, and also the multipliers kr = k0 + 11184810r  for r = 1, 2, 3, . . . Such numbers are now called Riesel numbers because of their similarity with the Sierpiński numbers. Note that k0 is a prime number. The Riesel problem consists in determining the smallest Riesel number.

Conjecture. The integer k = 509203  is  the smallest Riesel number.

To prove the conjecture, it suffices to exhibit a prime k · 2n − 1 for each k < 509203. This has yet to be accomplished for the following 52 values of k:

      2293,     9221,   23669,   31859,   38473,   46663,   67117,   74699,   81041,   93839,  
    97139, 107347, 121889, 129007, 143047, 146561, 161669, 192971, 206039, 206231,  
  215443, 226153, 234343, 245561, 250027, 273809, 315929, 319511, 324011, 325123,  
  327671, 336839, 342847, 344759, 362609, 363343, 364903, 365159, 368411, 371893,  
  384539, 386801, 397027, 402539, 409753, 444637, 470173, 474491, 477583, 485557,  
  494743, 502573  

The latest update to the list is from December 28, 2013.

A reasonable approach to the Riesel problem is to determine the first exponent n giving a prime k · 2n − 1 in each case. So we can observe the exact rate at which the 254601 multipliers k < 509203 are successively eliminated, which may enable us to predict their further decrease by extrapolation.

In order to summarize the known results, let us define fm to be the number of multipliers k < 509203 giving their first prime k · 2n − 1 for an exponent n in the interval 2m < n < 2m+1. Then f0 = 39867 is the number of those k for which k · 2 − 1 is a prime, the first one being k = 3 (note that 1 · 2 − 1 = 1 is not considered to be a prime). More generally, the following frequencies have been determined:

  m fm
0   39867
1 59460
2 62311
3 45177
4 24478
5 11668
6 5360
7 2728
8 1337
9 785
10 467
         
  m fm
11   289
12 191
13 125
14 87
15 62
16 38
17 35
18 25
19 22
20 18
21 13

As a combined result of the above computations (including the correction), 71 values of k were left which had no prime k · 2n - 1 for n < 2097152 = 221. From these 71 undecided values of k another 8 have been eliminated by the Riesel Sieve Project, whose participants discovered primes k · 2n − 1 for the following pairs k, n :

k n Discoverer    Date
 26773  2465343    John Dalton & RSP  01 Dec 2006
 113983  3201175    Ian Keogh & RSP  01 May 2008
 114487  2198389    Bruce White & RSP  23 May 2006
 196597  2178109    Auritania Du & RSP  09 May 2006
 275293  2335007    Japke Rosink & RSP  21 Sep 2006
 342673  2639439    Dhumil Zaveri & RSP  28 Apr 2007
 450457  2307905    Jeff Smith & RSP  28 Mar 2006
 485767  3609357    Chris Cardall & RSP  24 Jun 2008

Following the unfortunate disappearence of the Riesel Sieve Project, the investigation was finally resumed at PrimeGrid, starting in March 2010: see The Riesel Problem. In this context, another 5 primes k · 2n − 1 having 2097152 ≤ n < 4194304 were discovered, as follows; the values of k are linked to PrimeGrid's Official Announcements:

k n Discoverer         Date
 65531  3629342    Adrian Schori & PrimeGrid  05 Apr 2011
 123547  3804809    Jakub Łuszczek & PrimeGrid  08 May 2011
 191249  3417696    Jonathan Pritchard & PrimeGrid  21 Nov 2010
 415267  3771929    Alexey Tarasov & PrimeGrid  08 May 2011
 428639  3506452    Brett Melvold & PrimeGrid  14 Jan 2011

On June 4, 2011 the search was completed to the limit n < 4194304 = 222 for all of the remaining 58 "Riesel number candidates", which finally established the value of f21 = 13 (see table of frequencies above). The search is continuing for n ≥ 4194304 and has currently covered all n < 6783000. The following additional primes have been found so far:

k n Discoverer         Date
 40597  6808509 Frank Meador & PrimeGrid  25 Dec 2013
 141941  4299438 Scott Brown & PrimeGrid  26 May 2011
 252191  5497878 Jan Haller & PrimeGrid  23 Jun 2012
 304207  6643565 Randy Ready & PrimeGrid  11 Oct 2013
 353159  4331116 Jaakko Reinman & PrimeGrid  31 May 2011
 398023  6418059    Vladimir Volynsky & PrimeGrid  05 Oct 2013

Overall, this leaves the 52 uncertain candidates listed at the beginning. The largest prime discovered during this investigation is the 2049571 -digit prime 40597 · 26808509 − 1.

References.

For more information see the Riesel number page in Chris Caldwell's Glossary.

Address questions about this web page to Wilfrid Keller


URL: http://www.prothsearch.net/rieselprob.html
Last modified: December 28, 2013.