The Sierpinski Problem: Definition and Status

In 1960 Waclaw Sierpinski (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 Sierpinski number. The Sierpinski problem consists in determining the smallest Sierpinski number. In 1962, John Selfridge discovered the Sierpinski number k = 78557, which is now believed to be in fact the smallest such number.

Conjecture. The integer k = 78557  is  the smallest Sierpinski number.

To prove the conjecture, it would be sufficient to exhibit a prime k.2n + 1 for each k < 78557.

Summary of results. This summary describes developments in the computational approach to a possible "solution" of the Sierpinski problem, from the earliest attempts in the late 1970ies until November 2002, and gives a comprehensive status of results known at that point.

For more recent information, refer to the distributed computing project Seventeen or Bust. The name of this project indicates that when it was created, only 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.

As long as a prime is not found for a listed k, that k might be considered a potential Sierpinski number. However, as the conjecture suggests, in the long run a prime is expected to emerge for each of these k.

When the paper [K1] was published in 1983 (see the references below), 69 values of k were known to give no prime k.2n + 1 for n < 8000. They included, of course, the above 17 candidates. The value of k = 2897 had been eliminated as early as 1981 with the larger prime 2897.29715 + 1. By August 1997, another 48 of those multipliers k had subsequently been discarded. For all these 49 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
2897 9715 BCW
3061 33288 BY
5297 50011 Y
5897 22619 K2 & BY
7013   126113 Y
7651 25368 BY
8423 55157 BY
13787 53135 Y
14027 40639 BY
16817 42155 BY
18107 21279 K2 & BY
20851 10672 K2 & BY
25819 111842 Y
27923 158625 Y
32161 43796 BY
34711 10464 K2 & BY
36983 38573 BY
37561 16604 K2 & BY
39079 26506 K2
39781 176088 Y
40547 12983 K2 & BY
44903 17913 K2 & BY
46187 104907 Y
46471 96640 Y
  47897 61871 Y
         
k n  Discoverers
49219 16102 K2 & BY
50693 32753 Y
51917 18031 BY
52771 9900 K2 & BY
53941 36944 BY
54001 16652 K2
54739 14282 K2 & BY
60443 95901 Y
60541   176340 Y
62093 18353 K2 & BY
62761 15064 K2 & BY
63017 53195 Y
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 Y
75841 31220 BY
76759 17446 K
77899 43194 BY
  78181 22024 BY

With the advent of Yves Gallot's powerful program Proth.exe in 1997, the search for primes could be further extended. As a result of intensified efforts, four multipliers k were eliminated in the sequel:

 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 long-term collaborative work by Joseph Arthur, Ray Ballinger, Didier Boivin, Chris Caldwell, Phil Carmody, Daval Davis, Jim Fougeron, 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.

To get an impression of the rate at which the 39278 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 2m < n < 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 observed:

m = 0 1 2 3 4 5 6 7 8 9 10 11 12
  fm =   7238   10194   9582   6272   3045   1445   685   331   195   114   47   34   26

From the above tables of primes and currently known search limits we infer that   f13 = 11,   f14 = 18,   f15 = 12,   f16 = 5,   f17 = 5  and   f18 > 2.

References.

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

Address questions about this web page to Ray Ballinger or to Wilfrid Keller.

Back to index Page


URL: http://www.prothsearch.net/sierp.html
Last modified: November 27, 2002.