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.
|
|
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.