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

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:

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

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 2²³ ≤ n < 2²⁴ = 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 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 14 candidates were removed by users of Gallot's program Proth.exe:

In October 2003, this investigation was restarted by the Prime Sierpinski Project, so far obtaining the following 14 primes:

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.

• [S] W. Sierpinski, Sur un problème concernant les nombres k · 2ⁿ + 1, Elem. Math. 15 (1960), 73-74.
• [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.
• [K1] W. Keller, Factors of Fermat numbers and large primes of the form k · 2ⁿ + 1, Math. Comp. 41 (1983), 661-673.
• [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.