Sierpinski number

From Wikipedia, the free encyclopedia

In number theory, a Sierpinski number is an odd natural number k such that integers of the form k2n + 1 are composite (i.e. not prime) for all natural numbers n.

In other words, when k is a Sierpinski number, all members of the following set are composite:

\left\{\,k 2^n + 1 : n \in\mathbb{N}\,\right\}.

Numbers in this set with odd k and k < 2n are called Proth numbers.

In 1960 Wacław Sierpiński proved that there are infinitely many odd integers that when used as k produce no primes.

Contents

[edit] The Sierpinski problem

The Sierpinski problem is: "What is the smallest Sierpinski number?"

In 1962, John Selfridge proved that 78,557 is a Sierpinski number; he showed that, when k=78,557, all numbers of the form k2n+1 have a factor in the covering set {3, 5, 7, 13, 19, 37, 73}.

In addition, in 1967, Sierpiński and Selfridge proposed (but could not prove) the conjecture that 78,557 is the smallest Sierpinski number, and thus the answer to the Sierpinski problem.

To show that 78,557 really is the smallest Sierpinski number, one must show that all the odd numbers smaller than 78,557 are not Sierpinski numbers. That is, there exists an n such that k2n+1 is prime.[1] As of November 2007, there are only six candidates which have not been eliminated as possible Sierpinski numbers.[2] Seventeen or Bust, a distributed computing project, is testing these remaining numbers.

If the project finds a prime of the right form for all the remaining k, the Sierpinski problem will be solved.

[edit] Solved k

A k value is solved when a prime of form k2n + 1 is found. Here are some cases where a large prime was needed to solve a k:

  1. k=4847 was solved when the number 4847 × 23321063 + 1 was found to be prime.(19 October 2005 )
  2. k=5359 was solved when the number 5359 × 25054502 + 1 was found to be prime.
  3. k=19249 was solved when the number 19249 × 213018586 + 1 was found to be prime.(5 May 2007 )
  4. k=27653 was solved when the number 27653 × 29167433 + 1 was found to be prime.(15 June 2005 )
  5. k=28433 was solved when the number 28433 × 27830457 + 1 was found to be prime.
  6. k=33661 was solved when the number 33661 × 27031232 + 1 was found to be prime.(30 October 2007 )
  7. k=44131 was solved when the number 44131 × 2995972 + 1 was found to be prime.
  8. k=46157 was solved when the number 46157 × 2698207 + 1 was found to be prime.
  9. k=54767 was solved when the number 54767 × 21337287 + 1 was found to be prime.
  10. k=65567 was solved when the number 65567 × 21013803 + 1 was found to be prime.
  11. k=69109 was solved when the number 69109 × 21157446 + 1 was found to be prime.

[edit] Remaining k

  1. 10223
  2. 21181
  3. 22699
  4. 24737
  5. 55459
  6. 67607

[edit] See also

[edit] External links