The Sierpiński Problem: Definition and Status

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 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 twelve prime multipliers

 k = 10223, 22699, 67607, 
79309, 79817, 90527, 152267, 156511, 168451, 222113, 225931, 237019.

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 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
597 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 14 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 14 primes:

 k  n Discoverer Date
  212565 212565 Morris Cox   19 Nov 2003
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

Overall, this leaves the nine undecided candidates k = 79309, 79817, 90527, 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.

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: February 10, 2010.