Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3).
Navigation
Topics Help • Register • News • History • How to • Sequences statistics • Template prototypes

Difference between revisions of "Sierpiński problem"

From Prime-Wiki
Jump to: navigation, search
(restored)
 
(link)
 
(17 intermediate revisions by 3 users not shown)
Line 1: Line 1:
The '''Sierpinski problem''' in [[number theory]] was proposed by [[Waclaw Sierpinski]] in 1960.
+
{{Spelling|Sierpinski}}
 +
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''&times;2<sup>''n''</sup> + 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]]'''.
+
Consider numbers of the form {{V|N}} = {{Kbn|+|k|n}}, where {{Vk}} is odd and {{Vn}} > 0. If, for some fixed {{Vk}}, every integer {{Vn}} yields a [[composite number]] {{V|N}}, then {{Vk}} is said to be a '''[[Sierpiński number]]'''.
  
The Sierpinski problem, simply put, is: What is the '''smallest''' Sierpinski number?
+
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 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''.
+
[[John L. Selfridge]] proved in 1962 that {{Vk}} = 78557 is a Sierpiński number. The proof shows that every choice of {{Vn}} falls into at least one of seven categories, where each category guarantees a factor of {{V|N}}.
  
 
Since:
 
Since:
*<math>78557*2^{2n}+1</math> is multiple of 3.
+
*{{Kbn|+|78557|2n}} is multiple of 3.
*<math>78557*2^{4n+1}+1</math> is multiple of 5.
+
*{{Kbn|+|78557|4n+1}} is multiple of 5.
*<math>78557*2^{3n+1}+1</math> is multiple of 7.
+
*{{Kbn|+|78557|3n+1}} is multiple of 7.
*<math>78557*2^{12n+11}+1</math> is multiple of 13.
+
*{{Kbn|+|78557|12n+11}} is multiple of 13.
*<math>78557*2^{18n+15}+1</math> is multiple of 19.
+
*{{Kbn|+|78557|18n+15}} is multiple of 19.
*<math>78557*2^{36n+27}+1</math> is multiple of 37.
+
*{{Kbn|+|78557|36n+27}} is multiple of 37.
*<math>78557*2^{9n+3}+1</math> is multiple of 73.
+
*{{Kbn|+|78557|9n+3}} 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:
 
(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:
Line 29: Line 30:
 
|}
 
|}
  
So all exponents are covered, meaning that no member of the sequence <math>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.
+
So all exponents are covered, meaning that no member of the sequence {{Kbn|+|78557|n}} 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.
+
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 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.
+
To prove it, we have to show that every number {{Vk}} < 78557 is not a Sierpiński number. Remember, a Sierpiński number is a fixed {{Vk}} such that all {{Vn}} yield composite {{V|N}}. So a non-Sierpiński number is a fixed {{Vk}} such that some choice of {{Vn}} yields a prime {{V|N}}. This turns out to be relatively easy to do for most choices of {{Vk}}. However, sometimes {{Vn}} 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 {{Vk}}. At that point, the [[Seventeen or Bust]] project began a systematic distributed computing search of the remaining {{Vk}} 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.
+
Currently [[PrimeGrid Seventeen or Bust|PrimeGrid]] is searching the remaining {{Vk}}-values.
  
 
==The remaining candidates==
 
==The remaining candidates==
As of 2017-05-09 the remaining ''k'' candidates are 21181, 22699, 24737, 55459, and 67607.
+
As of 2020-06-01 the remaining {{Vk}} candidates are [[Proth prime 2 21181|21181]], [[Proth prime 2 22699|22699]], [[Proth prime 2 24737|24737]], [[Proth prime 2 55459|55459]], and [[Proth prime 2 67607|67607]] (current status [https://www.primegrid.com/stats_sob_llr.php here]).
  
 
==Recent finds==
 
==Recent finds==
*[https://primes.utm.edu/primes/page.php?id=122473 10223 &times; 2<sup>31172165</sup> + 1] on [https://www.primegrid.com/download/SOB-31172165.pdf 2016-10-16]
+
*{{NPr|10223|31172165}} ({{T5000|122473|{{Num|9383761}} digits}}) on 2016-10-31 ([https://www.primegrid.com/download/SOB-31172165.pdf Official Announcement])
 +
*{{NPr|33661|7031232}} ({{T5000|82804|{{Num|2116617}} digits}}) on 2007-10-30
 +
*{{NPr|19249|13018586}} ({{T5000|80385|{{Num|3918990}} digits}}) on 2007-05-07
 +
*{{NPr|4847|3321063}} ({{T5000|75994|{{Num|999744}} digits}}) on 2005-10-21
 +
*{{NPr|27653|9167433}} ({{T5000|74836|{{Num|2759677}} digits}}) on 2005-06-08
 +
*{{NPr|28433|7830457}} ({{T5000|73145|{{Num|2357207}} digits}}) on 2004-12-31
 +
*{{NPr|5359|5054502}} ({{T5000|67719|{{Num|1521561}} digits}}) on 2003-12-06
 +
*{{NPr|54767|1337287}} ({{T5000|62869|{{Num|402569}} digits}}) on 2002-12-22
 +
*{{NPr|69109|1157446}} ({{T5000|62868|{{Num|348431}} digits}}) on 2002-12-06
 +
*{{NPr|44131|995972}} ({{T5000|62867|{{Num|299823}} digits}}) on 2002-12-05
 +
*{{NPr|65567|1013803}} ({{T5000|62866|{{Num|305190}} digits}}) on 2002-12-02
 +
*{{NPr|46157|698207}} ({{T5000|62865|{{Num|210186}} digits}}) on 2002-11-27
  
 
==See also==
 
==See also==
 +
*[[Riesel problem 1|Riesel problem]]
 
*[[PrimeGrid]]
 
*[[PrimeGrid]]
*[[Seventeen Or Bust]]
+
*[[Seventeen or Bust]]
  
 
==External links==
 
==External links==
*[http://web.archive.org/web/20160405211049/http://seventeenorbust.com:80/ WebArchive] of [[Seventeen Or Bust]] project page as of 2016-04-05
+
*[http://web.archive.org/web/20160405211049/http://seventeenorbust.com:80/ WebArchive] of [[Seventeen or Bust]] project page as of 2016-04-05
*[http://www.prothsearch.com/sierp.html The Sierpiński Problem]: Definition and Status at [http://www.prothsearch.com/ Proth Search Page] (outdated)
+
*[http://www.prothsearch.com/sierp.html The Sierpiński Problem]: Definition and Status at [http://www.prothsearch.com/ Proth Search Page] (outdated)
 
*[http://mathworld.wolfram.com/SierpinskiNumberoftheSecondKind.html Mathworld page]
 
*[http://mathworld.wolfram.com/SierpinskiNumberoftheSecondKind.html Mathworld page]
*[https://en.wikipedia.org/wiki/Sierpinski_number#Sierpi.C5.84ski_problem Wikipedia]
+
*[[Wikipedia:Sierpiński_number#Sierpi.C5.84ski_problem|Sierpiński problem]]
 
*[https://www.primegrid.com/forum_thread.php?id=972 Thread] at PrimeGrid
 
*[https://www.primegrid.com/forum_thread.php?id=972 Thread] at PrimeGrid
[[Category:Math]]
+
[[Category:Conjectures]]
[[Category:Distributed computing projects]]
+
[[Category:Distributed computing project]]

Latest revision as of 10:25, 26 March 2024

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•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 L. 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 2020-06-01 the remaining k candidates are 21181, 22699, 24737, 55459, and 67607 (current status here).

Recent finds

See also

External links