The Sierpiński Problem: Definition and Status

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, 193997, 200749, 
202705, 209611, 227723, 229673, 238411.

Updated  June 9, 2014 (small correction).

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.

k n  Discoverers
3061 33288 BY
5297 50011 Y2
5897 22619 K2 & BY
7013   126113 Y2
7651 25368 BY
8423 55157 BY
13787 53135 Y2
14027 40639 BY
16817 42155 BY
18107 21279 K2 & BY
20851 10672 K2 & BY
25819 111842 Y2
27923 158625 Y2
32161 43796 BY
34711 10464 K2 & BY
36983 38573 BY
37561 16604 K2 & BY
39079 26506 K2
39781 176088 Y2
40547 12983 K2 & BY
44903 17913 K2 & BY
46187 104907 Y2
46471 96640 Y2
  47897 61871 Y2
         
k n  Discoverers
49219 16102 K2 & BY
50693 32753 Y1
51917 18031 BY
52771 9900 K2 & BY
53941 36944 BY
54001 16652 K2
54739 14282 K2 & BY
60443 95901 Y2
60541   176340 Y2
62093 18353 K2 & BY
62761 15064 K2 & BY
63017 53195 Y2
64007 26015 BY
65057 8899 K2 & BY
67193 16249 K2
67759 10402 K2 & BY
69107 16599 K2 & BY
71417 26807 BY
71671 28884 BY
74191 20340 Y1
75841 31220 BY
76759 17446 K2
77899 43194 BY
  78181 22024 BY

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 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 2mn < 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:

  m   fm
0 7238
1   10194
2 9582
3 6272
4 3045
5 1445
6 685
7 331
8 195
9 114
10 47
11 34
         
  m  fm
12   26
13 11
14 18
15 12
16 5
17 5
18 2
19 3
20 2
21 1
22 3
23 ≥ 2

The search for the interval 223n < 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 2mn < 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:

 m  fm
0 1667
1   2804
2 3635
3 3242
4 2140
5 1145
6 605
7 322
         
  m  fm
8   159
9 106
10 59
11 45
12 23
13 17
14 12
15 5

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:

 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:

  m  fm
16   12
17 5
18 5
19 6
         
  m  fm
20   3
21 1
22 2
23  ≥ 1

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 2mn < 2m+1. Then we determined the following frequencies:

 m    fm"
0 13491
1   19709
2 19803
3 13909
4 7193
5 3197
6 1451
7 656
         
  m  fm"
8   364
9 162
10 99
11 67
12 42
13 30
14 23
15 14

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.

 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 18 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
  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, 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 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.

References.

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

Address questions about this web page to Wilfrid Keller.


URL: http://www.prothsearch.net/sierp.html
Last modified: June 9, 2014.