The Riesel Problem: Definition and Status

Compiled by Wilfrid Keller

In 1956 Hans Riesel (1929−2014) proved the following interesting result.

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

Actually, Riesel showed that k₀ = 509203 has this property, and also the multipliers k_r = k₀ + 11184810r  for r = 1, 2, 3, . . . Such numbers are now called Riesel numbers because of their similarity with the Sierpiński numbers. Note that k₀ 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 · 2ⁿ − 1 for each k < 509203. This has yet to be accomplished for the following 42 values of k:

23669,   31859,   38473,   46663,   67117,   74699,   81041, 107347, 121889, 129007,

143047, 161669, 206231, 215443, 226153, 234343, 245561, 250027, 315929, 319511,

324011, 325123, 327671, 336839, 342847, 344759, 362609, 363343, 364903, 365159,

368411, 371893, 384539, 386801, 397027, 409753, 444637, 470173, 474491, 477583,

485557, 494743

The latest update to the list is from May 1st, 2023.

A reasonable approach to the Riesel problem is to determine the first exponent n giving a prime k · 2ⁿ − 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 f_m to be the number of multipliers k < 509203 giving their first prime k · 2ⁿ − 1 for an exponent n in the interval 2^m < n < 2^m+1. Then f₀ = 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 so far:

m fm 0   39867 1 59460 2 62311 3 45177 4 24478 5 11668 6 5360 7 2728 8 1337 9 785 10 467 11 289 12   191

m fm 13   125 14 87 15 62 16 38 17 35 18 25 19 22 20 18 21 13 22 8 23 ≥ 7 24 ≥ 1

• The frequencies f_m for m < 10 were first computed by Wilfrid Keller in 1992 and independently verified by Yves Gallot, who extended the computations to m < 13. This range was finished on May 11, 1998.
   
• Later on, Ray Ballinger, Wilfrid Keller, and Skip Key determined that f₁₄ = 87, by finding 21, 25, and 41 first primes, respectively, having 16384 < n < 32768. These computations were finished on November 14, 1998.
   
• On April 9, 1999 the value of f₁₅ = 62 (corrected May 12, 1999, and April 20, 2000) was established. The corresponding primes k · 2ⁿ − 1 with 32768 < n < 65536 were found by Ray Ballinger (5 primes), Kenneth Brazier (1 prime), Chris Caldwell (2 primes), Wilfrid Keller (13 primes), Skip Key (22 primes), Tom Kuechler (1 prime), and Dave Linton (18 primes). Other contributors to this segment were David Anderson, Chad Davis, Yves Gallot, Michal Misztal, Anton Oleynick, Michael Peake, Janusz Szmidt, and Helmut Zeisel.
   
• On October 22, 1999 the value of f₁₆ = 38 was established. The corresponding primes k · 2ⁿ − 1 with 65536 < n < 131072 were found by Ray Ballinger (2 primes), Yves Gallot (1 prime), Wilfrid Keller (4 primes), Skip Key (5 primes), Dave Linton (25 primes), and Helmut Zeisel (1 prime). Other contributors to this segment were David Anderson, Chris Caldwell, Tom Kuechler, Michal Misztal, and Anton Oleynick.
   
• On July 13, 2001 the value of f₁₇ = 35 was established. The corresponding primes k · 2ⁿ − 1 with 131072 < n < 262144 were found by Andres Aitsen (1 prime), Ray Ballinger (2 primes), Lew Baxter (1 prime), Yves Gallot (1 prime), Olivier Haeberlé (1 prime), Richard Heylen (1 prime), Dave Linton (25 primes), Patrick Pirson (1 prime), Janusz Szmidt (1 prime), and Helmut Zeisel (1 prime). Other contributors to this segment were David Anderson, Steven Harvey, Wilfrid Keller, Skip Key, David Kokales, Tom Kuechler, Eugen Muischnek, Kevin O'Hare, Anton Oleynick, and Steven Whitaker.
   
• On December 4, 2003 the value of f₁₈ = 25 was established. The corresponding primes k · 2ⁿ − 1 with 262144 < n < 524288 were found by Dale Andrews (1 prime), Ray Ballinger (4 primes), Daval Davis (1 prime), Olivier Haeberlé (1 prime), Richard Heylen (2 primes), Reto Keiser (1 prime), Tom Kuechler (1 prime), Nuutti Kuosa (1 prime), Dave Linton (6 primes), Patrick Pirson (1 prime), Mark Rodenkirch (1 prime), Lucas Schmid (1 prime), Janusz Szmidt (2 primes), Jeff Wolfe (1 prime), and Helmut Zeisel (1 prime), and are specified as follows:
  
  

  k	n	Discoverer	Date
  27253	272347	Ray Ballinger	10 Oct 1998
  39269	287048	Richard Heylen	25 Mar 2002
  42779	322908	Ray Ballinger	26 Jul 1999
  43541	507098	Ray Ballinger	01 Oct 2000
  46271	428210	Patrick Pirson	29 Apr 2001
  104917	340181	Janusz Szmidt	13 Nov 1999
  130139	280296	Dale Andrews	02 Feb 2002
  144643	498079	Richard Heylen	12 Dec 2000
  148901	360338	Mark Rodenkirch	05 Mar 2002
  159371	284166	Janusz Szmidt	14 Jan 2002
  189463	324103	Dave Linton	15 Jul 2000
  201193	457615	Daval Davis	03 Feb 2003
  220063	306335	Olivier Haeberlé	03 Sep 1999
  235601	295338	Helmut Zeisel	06 Mar 2003
  245051	285750	Tom Kuechler	15 Nov 2000
  267763	264115	Dave Linton	19 Feb 2000
  277153	429819	Jeff Wolfe	21 Nov 2002
  299617	428917	Dave Linton	22 Jul 2002
  376993	293603	Reto Keiser	08 Sep 2002
  382691	431722	Ray Ballinger	27 Feb 2003
  398533	419107	Dave Linton	04 Sep 2002
  401617	470149	Dave Linton	27 Dec 2002
  416413	424791	Dave Linton	28 Apr 2003
  443857	369457	Nuutti Kuosa	27 Aug 2001
  465869	497596	Lucas Schmid	27 Jan 2003

  
  Other contributors to this segment were Claude Abraham, Andres Aitsen, Torbjörn Alm, David Anderson, Brian Beesley, Chris Florin, Steven Harvey, Richard Kapek, Craig Kitchen, David Kokales, Michael Kwok, Eugen Muischnek, Kevin O'Hare, Anton Oleynick, Daniel Papp, Thomas Ritschel, Steve Scott, Peter Shaw, Jiong Sun, Andrew Walker, Steven Whitaker, and Thomas Wolter.
  
  
• On September 23, 2004 the value of f₁₉ = 21 was established. The corresponding primes k · 2ⁿ − 1 with 524288 < n < 1048576 were found by Olivier Haeberlé (10 primes), the Riesel Sieve Project (7 primes), Ray Ballinger (1 prime), Richard Heylen (1 prime), Dave Linton (1 prime), and Lucas Schmid (1 prime), and are specified as follows:
  
  

  k	n	Discoverer	Date
  659	800516	Dave Linton	01 Mar 2004
  89707	578313	Richard Heylen	02 Apr 2003
  93997	864401	Guido Stolz & RSP	01 Apr 2004
  98939	575144	Olivier Haeberlé	30 Nov 2001
  103259	615076	Olivier Haeberlé	23 Dec 2002
  109897	630221	Olivier Haeberlé	22 Apr 2003
  126667	626497	Ray Ballinger	09 Jun 2003
  170591	866870	Drew Bishop & RSP	15 Apr 2004
  204223	696891	Olivier Haeberlé	23 Mar 2003
  212893	730387	Olivier Haeberlé	15 Oct 2003
  215503	649891	Olivier Haeberlé	28 Apr 2003
  220033	719731	Olivier Haeberlé	19 Apr 2004
  222997	613153	Olivier Haeberlé	28 Nov 2001
  246299	752600	Kevin O'Hare & RSP	23 Jan 2004
  261221	689422	Sean Faith & RSP	22 Dec 2003
  279703	616235	Dhumil Zaveri & RSP	07 Jan 2004
  309817	901173	Helmut Michel & RSP	07 Jun 2004
  357491	609338	Lucas Schmid	17 Jan 2003
  401143	532927	Olivier Haeberlé	11 Jun 2003
  458743	547791	Olivier Haeberlé	22 Oct 2003
  460139	779536	Drew Bishop & RSP	26 Mar 2004

  
  Other contributors to this segment, not lucky enough to meet a prime, were Claude Abraham, Dale Andrews, Rolan Christofferson, Tom Ehlert, Chris Florin, Jason Fraser, Reto Keiser, Craig Kitchen, Tom Kuechler, Michael Kwok, Kent McArthur, Eugen Muischnek, Kevin O'Hare, Jean Penné, Patrick Pirson, Thomas Ritschel, Steve Scott, Guido Smetrijns, Jiong Sun, Randy Wilson, Jeff Wolfe, Thomas Wolter, and Helmut Zeisel.
  
  In a double check effort initiated by the PrimeGrid group in January 2012, a prime was found that had been missed during this stage of the investigation, namely:
  
  

  k	n	Discoverer	Date
  162941	993718	Dmitry Domanov & PrimeGrid	02 Feb 2012

  
  As a consequence, the corresponding number of eliminations had to be corrected to give f₁₉ = 22. We note that the missing prime occurred in an interval originally covered by one of the individual participants working independently of RSP.
  

• The next stage of this investigation was completed under the direction of the Riesel Sieve Project. The value of f₂₀ = 18 was established probably near the end of 2007. The corresponding primes k · 2ⁿ − 1 with 1048576 < n < 2097152 are specified as follows:
  

  k	n	Discoverer	Date
  71009	1185112	Drew Bishop & RSP	05 Dec 2004
  110413	1591999	Will Fisher & RSP	08 Jun 2005
  149797	1414137	Peter van Hoof & RSP	13 Mar 2005
  150847	1076441	Darren Wallace & RSP	15 Aug 2004
  152713	1154707	Ray Ballinger	23 Oct 2004
  192089	1395688	Guido Stolz & RSP	10 May 2004
  234847	1535589	Darren Wallace & RSP	09 May 2005
  325627	1472117	Will Fisher & RSP	05 Apr 2005
  345067	1876573	Dave Linton	13 Nov 2005
  350107	1144101	Sean Faith & RSP	24 Oct 2004
  357659	1779748	Drew Bishop & RSP	25 Sep 2005
  412717	1084409	Holger Meissner & RSP	22 Aug 2004
  417643	1800787	Greg Childers & RSP	05 Oct 2004
  467917	1993429	Steven Wong & RSP	25 Dec 2005
  469949	1649228	Steven Wong & RSP	28 Oct 2007
  500621	1138518	Darren Wallace & RSP	18 Oct 2004
  502541	1199930	Ryan Sefko & RSP	21 Dec 2004
  504613	1136459	Magnus Mischel & RSP	17 Oct 2004

  As a combined result of the above computations (including the correction), 71 values of k were left which had no prime k · 2ⁿ - 1 for n < 2097152 = 2²¹. From these 71 undecided values of k another 8 have been eliminated by the Riesel Sieve Project, whose participants discovered primes k · 2ⁿ − 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 · 2ⁿ − 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 reached the limit n < 4194304 = 2²² for all of the remaining 58 "Riesel number candidates", which finally established the value of f₂₁ = 13.

• The next segment for n, 4194304 ≤ n < 8388608 = 2²³, was completed in May 2017, after providing the following primes relevant to the Riesel problem:

  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
  402539	7173024	Walter Darimont & PrimeGrid	02 Oct 2014
  502573	7181987	Denis Iakovlev & PrimeGrid	04 Oct 2014

  with the count of f₂₂ = 8 (compare the table of frequencies above).

• The search was continuing for n ≥ 8388608 and had covered all n < 11534000 by April 2021. Below that limit, the following three primes had already been found:

  k	n	Discoverer	Date
  9221	11392194	Barry Schnur & PrimeGrid	07 Feb 2021
  146561	11280802	Pavel Atnashev & PrimeGrid	16 Nov 2020
  273809	8932416	Wolfgang Schwieger & PrimeGrid	13 Dec 2017

  However, five even larger primes were subsequently reported by an independent researcher:

  k	n	Discoverer	Date
  2293	12918431	Ryan Propper	13 Feb 2021
  93839	15337656	Ryan Propper	27 Nov 2022
  97139	18397548	Ryan Propper	23 Apr 2023
  192971	14773498	Ryan Propper	07 Mar 2021
  206039	13104952	Ryan Propper	26 Apr 2021

  In these cases it is not known whether the given primes are the smallest ones in their respective sequences, as the search was temporarily stopped near n = 11534000, 13977000, 14450000, 11534000, and 11629000, respectively. For all the other 42 uncertain candidates listed at the beginning, the coordinated search has currently reached n < 14447000. Under these circumstances, the last two entries in the table of frequencies should be regarded with caution. Obviously, the largest prime discovered during this investigation is the recent 5538219-digit prime 97139 · 2^18397548 − 1.

References.