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 · 2n + 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 · 2n + 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 · 2n + 1 for each prime value k < 271129. Currently, a prime k · 2n + 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, 12 additional multipliers remain to be eliminated, which are the composite integers
k = 91549, 99739, 131179, 161041, 163187,
202705, 209611, 227723, 229673, 238411.
Updated March 12, 2013.
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 · 2n + 1 for n ≤ 8000. They included the value of k = 2897, which had been eliminated as early as 1981 with the larger prime 2897 · 29715 + 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 · 2n + 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:
|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,
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:
|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 3918990-digit prime 19249 · 213018586 + 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 fm to be the number of these k giving their first prime k · 2n + 1 for an exponent n in the interval 2m ≤ n < 2m+1. Then f0 = 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 223 ≤ n < 224 = 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 fm′ be the number of these k giving their first prime k · 2n + 1 for an exponent n in the interval 2m ≤ n < 2m+1. Then f0′ = 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 · 2n + 1 with n < 216 = 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:
|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:
|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 fm" be the number of composite values k such that the exponent n of the first prime k · 2n + 1 in the respective sequence satisfies 2m ≤ n < 2m+1. Then we determined the following frequencies:
This leaves 46 composite values of k such that there is no prime k · 2n + 1 with n < 216 = 65536. Furthermore, from Chris Caldwell's prime database (and one recent addition) we learned that for 16 of these multipliers a prime with n ≥ 216 was already known, as listed below.
|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 18 primes have been found:
|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|
|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 12 values of k no prime k · 2n + 1 exists for n < 3211000, and for these the search is continuing:
k = 91549, 99739, 131179, 161041, 163187,
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 26 candidates k < 271129, of which 11 are prime (see above) and 15 are composite. The latter include k = 21181, 24737, 55459 from the original Sierpiński problem.
For more information see the Sierpinski number page in Chris Caldwell's Glossary.
Address questions about this web page to Wilfrid Keller.