Sierpiński problem

The Sierpiński problem in number theory was proposed by Wacław Sierpiński in 1960.

The Problem

A definition:

Consider numbers of the form N = k•2ⁿ+1, where k is odd and n > 0. If, for some fixed k, every integer n yields a composite number N, then k is said to be a Sierpiński number.

The Sierpiński problem, simply put, is: What is the smallest Sierpiński number?

The conjecture

John Selfridge proved in 1962 that k = 78557 is a Sierpiński number. The proof shows that every choice of n falls into at least one of seven categories, where each category guarantees a factor of N.

Since:

• 78557•2²ⁿ+1 is multiple of 3.
• 78557•2⁴ⁿ⁺¹+1 is multiple of 5.
• 78557•2³ⁿ⁺¹+1 is multiple of 7.
• 78557•2¹²ⁿ⁺¹¹+1 is multiple of 13.
• 78557•2¹⁸ⁿ⁺¹⁵+1 is multiple of 19.
• 78557•2³⁶ⁿ⁺²⁷+1 is multiple of 37.
• 78557•2⁹ⁿ⁺³+1 is multiple of 73.

(those values form a covering set of {3, 5, 7, 13, 19, 37, 73}) we can prepare the following table for the exponents modulo 36:

exponent ≡	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35
multiple of	3	5	3	73	3	5	3	7	3	5	3	13	3	5	3	19	3	5	3	7	3	5	3	13	3	5	3	37	3	5	3	7	3	5	3	13

So all exponents are covered, meaning that no member of the sequence 78557•2ⁿ+1 can be prime. The same arguments can be said of the numbers 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909, 965431, 1259779, 1290677, 1518781, 1624097, 1639459, 1777613, 2131043, and so on.

Most mathematicians believe that 78557 is, indeed, the smallest Sierpiński number.

The hopes for a proof

To prove it, we have to show that every number k < 78557 is not a Sierpiński number. Remember, a Sierpiński number is a fixed k such that all n yield composite N. So a non-Sierpiński number is a fixed k such that some choice of n yields a prime N. This turns out to be relatively easy to do for most choices of k. However, sometimes n has to grow very large before a prime number appears.

In early 2002, primes had been found for all but seventeen choices of k. At that point, the Seventeen or Bust project began a systematic distributed computing search of the remaining k values. The community is divided on the question of whether or not it is likely the Seventeen or Bust project will complete its search within its authors' lifetimes. Heuristics have been used to estimate the range of numbers that must be tested before eliminating all the remaining multipliers is likely, but most of these heuristics have been demonstrated to be inaccurate. In any case, it is very likely that Seventeen Or Bust will be able to eliminate at least some of the remaining eight.

Currently PrimeGrid is searching the remaining k-values.

The remaining candidates

As of 2020-06-01 the remaining k candidates are 21181, 22699, 24737, 55459, and 67607 (current status here).

Recent finds

• Proth 10223•2^31172165+1 (9,383,761 digits) on 2016-10-31 (Official Announcement)
• Proth 33661•2^7031232+1 (2,116,617 digits) on 2007-10-30
• Proth 19249•2^13018586+1 (3,918,990 digits) on 2007-05-07
• Proth 4847•2^3321063+1 (999,744 digits) on 2005-10-21
• Proth 27653•2^9167433+1 (2,759,677 digits) on 2005-06-08
• Proth 28433•2^7830457+1 (2,357,207 digits) on 2004-12-31
• Proth 5359•2^5054502+1 (1,521,561 digits) on 2003-12-06
• Proth 54767•2^1337287+1 (402,569 digits) on 2002-12-22
• Proth 69109•2^1157446+1 (348,431 digits) on 2002-12-06
• Proth 44131•2⁹⁹⁵⁹⁷²+1 (299,823 digits) on 2002-12-05
• Proth 65567•2^1013803+1 (305,190 digits) on 2002-12-02
• Proth 46157•2⁶⁹⁸²⁰⁷+1 (210,186 digits) on 2002-11-27

See also

• Riesel problem
• PrimeGrid
• Seventeen or Bust

External links

• WebArchive of Seventeen or Bust project page as of 2016-04-05
• The Sierpiński Problem: Definition and Status at Proth Search Page (outdated)
• Mathworld page
• Sierpiński problem
• Thread at PrimeGrid