The Riesel Problem: Definition and Status

In 1956 Hans Riesel 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 Sierpinski numbers. 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. A reasonable approach to the 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:

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 21 20 18

• 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.
  
  
• The next stage of this investigation was completed under the direction of the Riesel Sieve Project. The value of f₂₀ = 18 was probably established 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 the overall result of the above computations, 72 values of k were left which had no prime k.2ⁿ - 1 for n < 2097152 = 2²¹. From these 72 uncertain values of k another 8 have been eliminated so far by the Riesel Sieve Project, whose participants discovered primes k.2ⁿ - 1 for the followng pairs k, n :

k	n	Discoverer	Date
26773	2465343	Anonymous & 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

The largest prime discovered during this investigation is the 1086531-digit prime 485767.2^3609357 - 1.

Here we give the 64 remaining "Riesel number candidates" k, as of September 2008:

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

References.

• H. Riesel, Några stora primtal (Swedish: Some large primes), Elementa 39 (1956), 258-260.
• W. Keller, Factors of Fermat numbers and large primes of the form k.2ⁿ + 1, II, unpublished manuscript, Hamburg, September 1992.
• Y. Gallot, unpublished data, 1998.
• Y. Gallot, On the number of primes in a sequence, http://perso.wanadoo.fr/yves.gallot/papers/, 2001.

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

Address questions about this web page to Wilfrid Keller