## 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 five values

k = 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 nine prime multipliers

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

Finally, the extended Sierpiński problem looks to see whether k = 271129 is actually the second smallest Sierpiński number. In order to prove this, 11 additional multipliers remain to be eliminated, which are the composite integers

k = 21181, 24737, 55459,
91549, 131179, 163187, 200749, 209611, 227723, 229673, 238411.

Updated  February 20, 2022.

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 = 10223, 21181, 22699, 24737, 55459, 67607. The eleven primes they found were:

 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 was the largest prime number discovered within that context.

Starting in 2010, PrimeGrid partnered with Seventeen or Bust to work towards solving the Sierpiński Problem. In April 2016, a server loss forced the project to cease operations. After the demise of the original Seventeen or Bust project, PrimeGrid is continuing by itself to pursue this investigation in looking to solve the Sierpiński Problem. A first remarkable success was experienced in discovering the following 9383761-digit prime, as detailed in the official announcement:

 k n Discoverer Date 10223 31172165 Péter Szabolcs 31 Oct 2016

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 12 26

 m fm 13 11 14 18 15 12 16 5 17 5 18 2 19 3 20 2 21 1 22 3 23 2 24 1

The search is ongoing for n > 225 = 33554432 and has so far covered all n < 36420000.

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, under whose direction the following 18 primes were found:

 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

In early 2008, the project started a cooperation with PrimeGrid, which led to the above primes for = 265711, 258317, and 90527. The Prime Sierpinski Project finally ceased operations, encouraging PrimeGrid to continue the search independently. Under these circumstances the following prime has already been found, as specified in the official announcement:

 k n Discoverer Date 168451 19375200 Ben Maloney 17 Sep 2017

Overall, this leaves the seven undecided candidates k = 79309, 79817, 152267, 156511, 222113, 225931, 237019, plus those two prime values k = 22699, 67607 having k < 78577, which were left by the original Seventeen or Bust project.

For the seven multipliers k > 78577, PrimeGrid reports having checked all n < 26686000. From all these findings we derive the next frequencies fm:

 m fm′ 16 12 17 5 18 5 19 6 20 3

 m fm′ 21 1 22 2 23 1 24 ≥ 1

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 (for k = 227753, discovered during the double checking process), the following 22 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 99739 14019102 Brian Niegocki 25 Dec 2019 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 193997 11452891 Tom Greer 03 Apr 2018 202705 21320516 Pavel Atnashev 25 Nov 2021 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 8 composite values of k no prime k · 2n + 1 exists for n < 21734000, and for these the search is continuing:

k = 91549, 131179, 163187, 200749, 209611, 227723, 229673, 238411.

This entails the following additional frequencies fm":
 m fm" 16 9 17 3 18 8 19 6 20 3

 m fm" 21 5 22 1 23 2 24 ≥ 1

To solve the extended Sierpiński problem, the most demanding of the three posed problems, would require the elimination of 20 candidates k < 271129, of which 9 are prime (look at the top of this page) and 11 are composite. The latter include  k = 21181, 24737, 55459  from the original Sierpiński problem.

References.

• [S] W. Sierpinski, Sur un problème concernant les nombres k · 2n + 1, Elem. Math. 15 (1960), 73-74.  PDF
• [M] N. S. Mendelsohn, The equation φ(x) = k, Math. Mag. 49 (1976), 37-39.
• [BCW] R. Baillie, G. Cormack and H. C. Williams, The problem of Sierpiński concerning k · 2n + 1, Math. Comp. 37 (1981), 229-231.  PDF
• [K1] W. Keller, Factors of Fermat numbers and large primes of the form k · 2n + 1, Math. Comp. 41 (1983), 661-673.  PDF
• [K2] W. Keller, The least prime of the form k · 2n + 1 for certain values of k, Abstracts Amer. Math. Soc. 9 (1988), 417-418.
• [BY] D. A. Buell and J. Young, Some large primes and the Sierpinski problem, SRC Technical Report 88-004, Supercomputing Research Center, Lanham, Maryland, May 1988.
• [Y1] J. Young, Primes submitted to Chris Caldwell's prime list, March 1993.
• [Y2] J. Young, Primes submitted to Chris Caldwell's prime list, August 1997.

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

URL: http://www.prothsearch.com/sierp.html