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 · 2ⁿ + 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ⁿ + 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 · 2ⁿ + 1 for each prime value k < 271129. Currently, a prime k · 2ⁿ + 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 · 2ⁿ + 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⁹⁷¹⁵ + 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ⁿ + 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:

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:

The 3918990-digit prime 19249 · 2^13018586 + 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:

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ⁿ + 1 for an exponent n in the interval 2^m ≤ n < 2^m+1. Then f₀ = 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 > 2²⁵ = 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 f_m′ be the number of these k giving their first prime k · 2ⁿ + 1 for an exponent n in the interval 2^m ≤ n < 2^m+1. Then f₀′ = 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 · 2ⁿ + 1 with n < 2¹⁶ = 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:

In October 2003, this investigation was restarted by the Prime Sierpinski Project, under whose direction the following 18 primes were found:

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:

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 f_m′:

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 f_m" be the number of composite values k such that the exponent n of the first prime k · 2ⁿ + 1 in the respective sequence satisfies 2^m ≤ n < 2^m+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 · 2ⁿ + 1 with n < 2¹⁶ = 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¹⁶ was already known, as listed below.

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:

It has also been determined that for the following 8 composite values of k no prime k · 2ⁿ + 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 f_m":

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 · 2ⁿ + 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 · 2ⁿ + 1, Math. Comp. 37 (1981), 229-231.  PDF 
• [K1] W. Keller, Factors of Fermat numbers and large primes of the form k · 2ⁿ + 1, Math. Comp. 41 (1983), 661-673.  PDF 
• [K2] W. Keller, The least prime of the form k · 2ⁿ + 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.

Address questions about this web page to Wilfrid Keller.