The Prime Glossary: Sierpinski number

Sierpinski number
(another Prime Pages' Glossary entries)

Glossary:

Prime Pages:

Top 5000:

A Sierpinski number is a positive, odd integer k for which the integers k^.2ⁿ+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^.2ⁿ+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 becase 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^.2ⁿ+1 prime (for that particular value of k):

10223, 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, 19294, 27653, 28433, 33661, 44131, 46157, 54767, 65567, and 69109! The prime they found for 19249 has 3,918,990 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^.2ⁿ-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· 2ⁿ+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 · 2ⁿ + 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, New York, NY, 1994. 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 · 2ⁿ +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 · 2ⁿ +1," Elem. Math., 15 (1960) 63-74. [See the glossary entry Sierpinski number as well as the paper [Riesel56].]