| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
| Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
Difference between revisions of "Sierpiński problem"
m |
m |
||
| Line 1: | Line 1: | ||
| − | The ''' | + | The '''Sierpiński problem''' in [[number theory]] was proposed by [[Wacław Sierpiński]] in 1960. |
==The Problem== | ==The Problem== | ||
A definition: | A definition: | ||
| − | Consider numbers of the form ''N = k × 2<sup>n</sup> + 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 '''[[ | + | Consider numbers of the form ''N = k × 2<sup>n</sup> + 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 | + | The Sierpiński problem, simply put, is: What is the '''smallest''' Sierpiński number? |
==The conjecture== | ==The conjecture== | ||
| − | [[John Selfridge]] proved in 1962 that ''k'' = 78557 is a | + | [[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: | Since: | ||
| Line 31: | Line 31: | ||
So all exponents are covered, meaning that no member of the sequence 78557*2<sup>n</sup>+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. | So all exponents are covered, meaning that no member of the sequence 78557*2<sup>n</sup>+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 | + | Most mathematicians believe that 78557 is, indeed, the smallest Sierpiński number. |
==The hopes for a proof== | ==The hopes for a proof== | ||
| − | To prove it, we have to show that every number ''k'' < 78557 is not a | + | 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. | 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. | ||
Revision as of 10:44, 20 February 2019
The Sierpiński problem in number theory was proposed by Wacław Sierpiński in 1960.
Contents
The Problem
A definition:
Consider numbers of the form N = k × 2n + 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*22n+1 is multiple of 3.
- 78557*24n+1+1 is multiple of 5.
- 78557*23n+1+1 is multiple of 7.
- 78557*212n+11+1 is multiple of 13.
- 78557*218n+15+1 is multiple of 19.
- 78557*236n+27+1 is multiple of 37.
- 78557*29n+3+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*2n+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 2017-05-09 the remaining k candidates are 21181, 22699, 24737, 55459, and 67607.
Recent finds
See also
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
