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.

If you want to participate in the search, please see the Search status for remaining candidates.

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

m fm 10   467 11 289 12 191 13 125 14 87 15 62 16 38 17 35 18 25 19 21

• 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	1998
  39269	287048	Richard Heylen	25 Mar 2002
  42779	322908	Ray Ballinger	1999
  43541	507098	Ray Ballinger	01 Oct 2000
  46271	428210	Patrick Pirson	29 Apr 2001
  104917	340181	Janusz Szmidt	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	2000
  201193	457615	Daval Davis	03 Feb 2003
  220063	306335	Olivier Haeberlé	1999
  235601	295338	Helmut Zeisel	06 Mar 2003
  245051	285750	Tom Kuechler	2000
  267763	264115	Dave Linton	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 finally 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	Riesel Sieve Project	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	Riesel Sieve Project	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	Riesel Sieve Project	23 Jan 2004
  261221	689422	Riesel Sieve Project	22 Dec 2003
  279703	616235	Riesel Sieve Project	07 Jan 2004
  309817	901173	Riesel Sieve Project	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	Riesel Sieve Project	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.

As the overall result of the above computations, 90 values of k were left which had no prime k.2ⁿ - 1 for n < 1048576 = 2²⁰. From these 90 uncertain values of k another 20 have been eliminated so far by finding primes k.2ⁿ - 1 for pairs k, n :

k	n	Discoverer	Date
71009	1185112	Riesel Sieve Project	05 Dec 2004
110413	1591999	Riesel Sieve Project	08 Jun 2005
114487	2198389	Riesel Sieve Project	23 May 2006
149797	1414137	Riesel Sieve Project	13 Mar 2005
150847	1076441	Riesel Sieve Project	15 Aug 2004
152713	1154707	Ray Ballinger	23 Oct 2004
192089	1395688	Riesel Sieve Project	10 May 2004
196597	2178109	Riesel Sieve Project	09 May 2006
234847	1535589	Riesel Sieve Project	09 May 2005
325627	1472117	Riesel Sieve Project	05 Apr 2005
345067	1876573	Dave Linton	13 Nov 2005
350107	1144101	Riesel Sieve Project	24 Oct 2004
357659	1779748	Riesel Sieve Project	25 Sep 2005
412717	1084409	Riesel Sieve Project	22 Aug 2004
417643	1800787	Riesel Sieve Project	05 Oct 2004
450457	2307905	Riesel Sieve Project	28 Mar 2006
467917	1993429	Riesel Sieve Project	25 Dec 2005
500621	1138518	Riesel Sieve Project	18 Oct 2004
502541	1199930	Riesel Sieve Project	21 Dec 2004
504613	1136459	Riesel Sieve Project	17 Oct 2004

The largest prime discovered during this investigation is the 694755-digit prime 450457.2^2307905 - 1.

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 Ray Ballinger or to Wilfrid Keller