Compiled by Wilfrid Keller
In 1960 Wacław Sierpiński (1882−1969) proved the following interesting result.
Theorem [S]. There exist infinitely many odd integers k such that k · 2^{n} + 1 is composite for every n ≥ 1.
A multiplier k with this property is called a Sierpiński number. The Sierpiński problem consists in determining the smallest Sierpiński number. In 1962, John Selfridge (1927−2010) discovered the Sierpiński number k = 78557, which is now believed to be in fact the smallest such number.
Conjecture. The composite integer k = 78557 = 17 · 4621 is the smallest Sierpiński number.
To prove the conjecture, it would be sufficient to exhibit a prime k · 2^{n} + 1 for each k < 78557. This has currently been achieved for all k, with the exception of the six values
k = 10223, 21181, 22699, 24737, 55459, 67607.
As long as a prime is not found for a listed k, that k might be considered a potential Sierpiński number. However, as the conjecture suggests, in the long run a prime is expected to emerge for each of these k.
In 1976, Nathan Mendelsohn (1917−2006) determined that the second provable Sierpiński number is the prime k = 271129 (see reference [M] below). The prime Sierpiński problem is to prove that this is the smallest prime Sierpiński number. To this end, it would be sufficient to exhibit a prime k · 2^{n} + 1 for each prime value k < 271129. Currently, a prime k · 2^{n} + 1 is not known for each of the 11 prime multipliers
_{ }k = 10223, 22699, 67607,_{ }
79309, 79817, 152267, 156511, 168451, 222113, 225931, 237019.
Finally, the extended Sierpiński problem looks to see whether k = 271129 is actually the second largest Sierpiński number. In order to prove this, 11 additional multipliers remain to be eliminated, which are the composite integers
_{ }k = 91549, 99739, 131179, 163187,
193997, 200749,_{ }
202705, 209611, 227723, 229673, 238411.
Updated January 10, 2015.
Summary of results. This summary first describes developments in the computational approach to a possible “solution” of the original Sierpiński problem, from the earliest attempts in the late 1970ies to the present.
When the paper [K1] was published in 1983 (see the references below), 70 values of k < 78557 were known to give no prime k · 2^{n} + 1 for n ≤ 8000. They included the value of k = 2897, which had been eliminated as early as 1981 with the larger prime 2897 · 2^{9715} + 1 [BCW]. By August 1997, another 48 of those multipliers k had subsequently been discarded. For these 48 values of k the smallest exponent n for a prime in the sequence k · 2^{n} + 1 is given in the next table. The initials for the discoverers again refer to the bibliographical items below. Note that 15 of the primes were published in [K2] and in [BY] independently.


With the advent of Yves Gallot's program Proth.exe, the search for primes could be extended more effectively, starting in August 1997. As a result, four multipliers k were eliminated:
k  n  Discoverer  Date 
34999  462058  Lew Baxter  11 Apr 2001 
48833  167897  Marc Thibeault  15 Mar 1999 
59569  390454  Janusz Szmidt  26 Nov 2001 
74269  167546  Marc Thibeault  25 Mar 1999 
These achievements were the outcome of a collaborative work by Joseph Arthur, Ray Ballinger, Lew Baxter, Didier Boivin, Chris Caldwell, Phil Carmody, Daval Davis, Jim Fougeron, Yves Gallot, Jason Gmoser, Olivier Haeberlé, Michael Hannigan, Wilfrid Keller, Robert Knight, Tom Kuechler, Dave Linton, Ian Lowman, Joe McLean, Marcin Lipinski, Tim Nikkel, Thomas Nøkleby, Andy Penrose, Michael Rödel, Martin Schroeder, Payam Samidoost, Pavlos Saridis, Janusz Szmidt, and Marc Thibeault.
In November 2002, “A Distributed Attack on the Sierpinski Problem” called Seventeen or Bust completely took over this investigation. The name of the project indicates that when it was created, just 17 uncertain candidates k were left to be investigated, namely,
k = 4847, 5359, 10223, 19249, 21181, 22699, 24737,
27653, 28433,
33661, 44131, 46157, 54767, 55459, 65567,
67607, 69109.
Within only a few weeks, the project succeeded in eliminating five of these candidates virtually at once. In the sequel, six more candidates were removed from the list, leaving the six values of k mentioned above. These are the primes they found:
k  n  Discoverer  Date 
4847  3321063  Richard Hassler  21 Oct 2005 
5359  5054502  Randy Sundquist  06 Dec 2003 
19249  13018586  Konstantin Agafonov  07 May 2007 
27653  9167433  Derek Gordon  08 Jun 2005 
28433  7830457  Anonymous  31 Dec 2004 
33661  7031232  Sturle Sunde  30 Oct 2007 
44131  995972  Anonymous  05 Dec 2002 
46157  698207  Stephen Gibson  27 Nov 2002 
54767  1337287  Peter Coels  22 Dec 2002 
65567  1013803  James Burt  02 Dec 2002 
69109  1157446  Sean DiMichele  06 Dec 2002 
The 3918990digit prime 19249 · 2^{13018586} + 1 is the largest prime number discovered during this investigation.
To get an impression of the rate at which the 39278 odd multipliers k < 78557 are successively eliminated, let us define f_{m} to be the number of these k giving their first prime k · 2^{n} + 1 for an exponent n in the interval 2^{m} ≤ n < 2^{m+1}. Then f_{0} = 7238 is the number of those k for which k · 2 + 1 is a prime, the first one obviously being k = 1. More generally, the following frequencies have been determined:


The search for the interval 2^{23} ≤ n < 2^{24} = 16777200 is still ongoing.
Regarding the prime Sierpiński problem, we might similarly determine the rate at which the 16029 prime multipliers k in the interval 78557 < k < 271129 are being eliminated. Let f_{m}′ be the number of these k giving their first prime k · 2^{n} + 1 for an exponent n in the interval 2^{m} ≤ n < 2^{m+1}. Then f_{0}′ = 1667 is the number of those k for which k · 2 + 1 is also a prime (these are Sophie Germain primes). The subsequent frequencies are also determined quite easily:


As a result, there remain 43 prime values of k such that there is no prime k · 2^{n} + 1 with n < 2^{16} = 65536. Of these, 34 have been eliminated in two stages. In the period from July 2000 to October 2001, the following 17 candidates were removed by users of Gallot's program Proth.exe:
k  n  Discoverer  Date 
101869  77002  Nestor Melo  31 Jul 2000 
115561  91548  Dirk Augustin  30 Jul 2000 
118081  145836  Kimmo Herranen  15 Dec 2000 
118249  80422  Pavlos Saridis  29 Jul 2000 
128239  88330  Nestor Melo  13 Oct 2000 
128449  109130  Nestor Melo  23 Oct 2000 
142099  70802  Dirk Augustin  08 Aug 2000 
147391  120616  Dirk Augustin  19 May 2001 
172157  71995  Kimmo Herranen  15 Dec 2000 
173933  340181  Kimmo Herranen  19 Jun 2001 
177421  69880  Kimmo Herranen  15 Dec 2000 
179581  117980  Kimmo Herranen  15 Dec 2000 
185993  164613  Kimmo Herranen  03 Nov 2000 
197753  73745  Kimmo Herranen  01 Sep 2000 
198647  178863  Kimmo Herranen  05 Nov 2000 
199037  101723  Kimmo Herranen  03 Sep 2000 
252181  149684  Sander Hoogendoorn  27 Oct 2001 
In October 2003, this investigation was restarted by the Prime Sierpinski Project, so far obtaining the following 18 primes:
k  n  Discoverer  Date 
87743  212565  Morris Cox  19 Nov 2003 
90527  9162167  Patrice Salah  30 Jun 2010 
122149  578806  Darren Wallace  19 Jan 2004 
149183  1666957  Lars Dausch  07 Oct 2005 
159503  540945  Darren Wallace  07 Feb 2004 
161957  727995  Darren Wallace  22 Mar 2004 
172127  448743  Harsh Aggarwal  05 Feb 2004 
203761  384628  Darren Wallace  05 Jan 2004 
214519  1929114  Lars Dausch  02 Jan 2006 
216751  903792  Lars Dausch  10 May 2004 
222361  2854840  Scott Yoshimura  31 Aug 2006 
224027  273967  Darren Wallace  12 Dec 2003 
241489  1365062  Harsh Aggarwal  24 Jan 2005 
247099  484190  Darren Wallace  05 Feb 2004 
258317  5450519  Scott Gilvey  27 Jul 2008 
261917  704227  Lars Dausch  08 Mar 2004 
263927  639599  Darren Wallace  20 Feb 2004 
265711  4858008  Scott Gilvey  07 Apr 2008 
From all these findings and the known search limits we derive the next frequencies:


Overall, this leaves the eight undecided candidates k = 79309, 79817, 152267, 156511, 168451, 222113, 225931, 237019, plus those three prime values k = 10223, 22699, 67607 having k < 78577, which are left in Seventeen or Bust. Both projects are in cooperation with PrimeGrid.
Now suppose that both Sierpiński problems treated above had finally been solved, showing that 78557 is the smallest Sierpiński number and that 271129 is the smallest prime Sierpiński number. This would not preclude the existence of a composite Sierpiński number k such that 78557 < k < 271129. So we might state an extended Sierpiński problem asking if 271129 is the second Sierpiński number, prime or not.
In this respect, we have gathered the following data concerning the 80256 odd composite values of k contained in the interval 78557 < k < 271129. Similar to the notation for prime multipliers k in that interval, let f_{m}" be the number of composite values k such that the exponent n of the first prime k · 2^{n} + 1 in the respective sequence satisfies 2^{m} ≤ n < 2^{m+1}. Then we determined the following frequencies:


This leaves 46 composite values of k such that there is no prime k · 2^{n} + 1 with n < 2^{16} = 65536. Furthermore, from Chris Caldwell's prime database (and one recent addition) we learned that for 16 of these multipliers a prime with n ≥ 2^{16} was already known, as listed below.
k  n  Discoverer  Date 
89225  92067  Daval Davis  08 Sep 2000 
138199  74670  Dirk Augustin  03 Aug 2000 
155357  79679  Dirk Augustin  03 Aug 2000 
165499  79638  James McElhatton  01 Sep 2000 
179791  331740  Kimmo Herranen  18 Jul 2001 
181921  148432  Kimmo Herranen  15 Dez 2000 
183347  116399  Nestor Melo  14 Aug 2000 
198113  267005  Kimmo Herranen  30 Apr 2001 
227753  91397  Lennart Vogel  13 Mar 2010 
231797  66503  Joseph McLean  11 Dec 2000 
237413  267149  Dan Morenus  03 Jun 2002 
240211  93184  Joseph McLean  26 Apr 2001 
250163  198453  Sander Hoogendoorn  19 Nov 2001 
255811  140148  Joseph McLean  30 Jun 2002 
263329  406934  Kevin O'Hare  05 Aug 2006 
270557  111807  Sander Hoogendoorn  20 Oct 2001 
For all these primes it has been verified that they are minimal in their respective sequences. The challenge was to find a prime for each of the remaining 30 values of k. This investigation was started in March 2010 in PrimeGrid's PRPNet: The extended Sierpinski problem. Along with the one prime above, the following 19 primes have been found:
k  n  Discoverer  Date 
85013  699333  Steve Martin  25 Mar 2010 
94373  3206717  Jörg Meili  10 Mar 2013 
98749  1045226  Rodger Ewing  09 Apr 2010 
107929  1007898  Brian Carpenter  05 Apr 2010 
123287  2538167  Timothy Winslow  14 Mar 2012 
147559  2562218  Rodger Ewing  27 Mar 2012 
154801  1305084  Rodger Ewing  29 Apr 2010 
161041  7107964  Martin Vanc  06 Jan 2015 
167957  417463  Brian Carpenter  21 Mar 2010 
168587  545971  Steve Martin  23 Mar 2010 
185449  435402  Rodger Ewing  21 Mar 2010 
187681  573816  Lennart Vogel  23 Mar 2010 
198677  2950515  Ardo van Rangelrooij  23 Oct 2012 
208381  463068  Lennart Vogel  22 Mar 2010 
211195  3224974  Ardo van Rangelrooij  11 Mar 2013 
219259  1300450  Lennart Vogel  29 Apr 2010 
225679  620678  Lennart Vogel  24 Mar 2010 
250463  1316921  Rodger Ewing  30 Apr 2010 
261203  354561  Lennart Vogel  20 Mar 2010 
It has also been determined that for the following 11 values of k no prime k · 2^{n} + 1 exists for n < 6870000, and for these the search is continuing:
_{ }k = 91549, 99739, 131179, 163187,
193997, 200749,_{ }
202705, 209611, 227723, 229673, 238411.
To solve the extended Sierpiński problem, the most demanding of the three posed problems, would require the elimination of 25 candidates k < 271129, of which 11 are prime (see above) and 14 are composite. The latter include k = 21181, 24737, 55459 from the original Sierpiński problem.
References.
For more information see the Sierpinski number page in Chris Caldwell's Glossary.
Address questions about this web page to Wilfrid Keller.