# Sierpinski number

A **Sierpinski number** is a positive, odd integer *k* for which the integers
*k*^{.}2^{n}+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^{n}+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*^{.}2^{n}+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*^{.}2^{n}-1 (see Riesel numbers).

**See Also:** RieselNumber

**Related pages** (outside of this work)

**References:**

- BCW1982
R. Baillie,G. CormackandH. C. Williams, "Corrigenda: "The problem of Sierpi\'nski concerningk· 2^{n}+1" [Math. Comp.37(1981), no. 155, 229--231],"Math. Comp.,39:159 (1982) 308.MR 83a:10006b- BCW81
Baillie, R.,Cormack, G.andWilliams, H.C., "The problem of Sierpinski concerningk· 2^{n}+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 smallestksuch thatk· 2^{n}+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 nombresk· 2^{n}+1,"Elem. Math.,15(1960) 63-74. [See the glossary entry Sierpinski number as well as the paper [Riesel56].]