Sierpiński problem

The Sierpinski 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|composite] (non-prime) number N, then k is said to be a Sierpinski number.

The Sierpinski problem, simply put, is: What is the smallest Sierpinski number?

The conjecture

John Selfridge proved in 1962 that k = 78557 is a Sierpinski 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:

• [math]\displaystyle{ 78557*2^{2n}+1 }[/math] is multiple of 3.
• [math]\displaystyle{ 78557*2^{4n+1}+1 }[/math] is multiple of 5.
• [math]\displaystyle{ 78557*2^{3n+1}+1 }[/math] is multiple of 7.
• [math]\displaystyle{ 78557*2^{12n+11}+1 }[/math] is multiple of 13.
• [math]\displaystyle{ 78557*2^{18n+15}+1 }[/math] is multiple of 19.
• [math]\displaystyle{ 78557*2^{36n+27}+1 }[/math] is multiple of 37.
• [math]\displaystyle{ 78557*2^{9n+3}+1 }[/math] 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 [math]\displaystyle{ 78557*2^n+1 }[/math] 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 Sierpinski number.

The hopes for a proof

To prove it, we have to show that every number k < 78557 is not a Sierpinski number. Remember, a Sierpinski number is a fixed k such that all n yield composite N. So a non-Sierpinski 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 2017-05-09 the remaining k candidates are 21181, 22699, 24737, 55459, and 67607.

Recent finds

• 10223 × 2^31172165 + 1 on 2016-10-16

See also

• 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
• Wikipedia
• Thread at PrimeGrid