Sierpinski number
A Sierpinski number is a positive, odd integer k for which the integers k.2n+1 are all composite (that is, for every positive integer n). In 1960 Sierpinski showed that there were infinitely many such numbers k (all solutions to a family of congruences), but he did not explicitly give a numerical example. The congruences provided a sufficient, but not necessary, condition for an integer to be a Sierpinski number. Of course Sierpinski also asked what the smallest such number might be--determining this number is called the Sierpinski problem.
If the congruences proposed by Sierpinski are solved, a 19-digit number k is obtained as their smallest solution. The much smaller example k = 78557, now conjectured to be the smallest Sierpinski number, was found by John Selfridge in 1962. This is a Sierpinski number because it has the "covering set:"
{3, 5, 7, 13, 19, 37, 73}
Why call this a covering set? Because every number of the form 78557.2n+1 is divisible by one of these small primes. So these seven primes cover every possible case!
| n | covering set |
|---|---|
| 78557 | {3, 5, 7, 13, 19, 37, 73} |
| 271129 | {3, 5, 7, 13, 17, 241} |
| 271577 | {3, 5, 7, 13, 17, 241} |
| 322523 | {3, 5, 7, 13, 37, 73, 109} |
| 327739 | {3, 5, 7, 13, 17, 97, 257} |
| 482719 | {3, 5, 7, 13, 17, 241} |
| 575041 | {3, 5, 7, 13, 17, 241} |
| 603713 | {3, 5, 7, 13, 17, 241} |
| 903983 | {3, 5, 7, 13, 17, 241} |
| 934909 | {3, 5, 7, 13, 19, 73, 109} |
| 965431 | {3, 5, 7, 13, 17, 241} |
| 1259779 | {3, 5, 7, 13, 19, 73, 109} |
| 1290677 | {3, 5, 7, 13, 19, 37, 109} |
| 1518781 | {3, 5, 7, 13, 17, 241} |
| 1624097 | {3, 5, 7, 13, 17, 241} |
| 1639459 | {3, 5, 7, 13, 17, 241} |
| 1777613 | {3, 5, 7, 13, 17, 19, 109, 433} |
| 2131043 | {3, 5, 7, 13, 17, 241} |
It is conjectured that 78557 is the smallest Sierpinski number because for most of the smaller numbers we can easily find a prime (in fact, for about 2/3rds of the numbers k there is a prime with n less than 9). The rest were then checked for small covering sets and none were found, so we expect to find a prime for the remaining forms.
To prove the Sierpinski conjecture, "all" you need to do is: for each of the following values of k, find an exponent n which makes k.2n+1 prime (for that particular value of k):
21181, 22699, 24737, 55459, and 67607.
Showing whether the list above is complete or not will take much more of this same type of prime finding.
The most recent and spectacular success on the Sierpinski problem is by the "Seventeen or Bust" project which has recently found primes for the multipliers 4847, 5359, 10223, 19294, 27653, 28433, 33661, 44131, 46157, 54767, 65567, and 69109! The prime they found for 10223 has 9,383,761 digits. It is expected that the primes for the last few multipliers will be very very large.
In 1956 Riesel studied the corresponding problem for numbers of the form k.2n-1 (see Riesel numbers).
See Also: RieselNumber
Related pages (outside of this work)
References:
- BCW1982
- R. Baillie, G. Cormack and H. C. Williams, "Corrigenda: "The problem of Sierpi\'nski concerning k· 2n+1" [Math. Comp. 37 (1981), no. 155, 229--231]," Math. Comp., 39:159 (1982) 308. MR 83a:10006b
- BCW81
- Baillie, R., Cormack, G. and Williams, H.C., "The problem of Sierpinski concerning k · 2n + 1," Math. Comp., 37:155 (1981) 229--231. MR 83a:10006a [Corrigenda: [BCW1982]]
- Guy94 (section B21)
- R. K. Guy, Unsolved problems in number theory, Springer-Verlag, 1994. New York, NY, ISBN 0-387-94289-0. MR 96e:11002 [An excellent resource! Guy briefly describes many open questions, then provides numerous references. See his newer editions of this text.]
- Jaeschke83
- G. Jaeschke, "On the smallest k such that k · 2n +1 are composite," Math. Comp., 40:181 (1983) 381--384. MR 84k:10006
- Keller91
- W. Keller, "Woher kommen die größten derzeit bekannten Primzahlen?," Mitt. Math. Ges. Hamburg, 12:2 (1991) 211-229. MR 92j:11006
- Riesel56
- H. Riesel, "Naagra stora primtal," Elementa, 39 (1956) 258-260. Swedish: Some large primes. [See the glossary entries Riesel number and Sierpinski number.]
- Sierpinski60
- W. Sierpinski, "Sur un probléme concernment les nombres k · 2n +1," Elem. Math., 15 (1960) 63-74. [See the glossary entry Sierpinski number as well as the paper [Riesel56].]