Sierpinski number
Encyclopedia
In number theory
, a Sierpinski or Sierpiński number is an odd natural number
k such that k2n + 1 is composite
, for all natural numbers n; in 1960, Wacław Sierpiński proved that there are infinitely many odd integer
s k which have this property.
In other words, when k is a Sierpinski number, all members of the following set are composite:
Numbers in this set with odd k and k < 2n are called Proth numbers.
The number 78,557 was proved to be a Sierpinski number by John Selfridge in 1962, who showed that all numbers of the form 78557·2n+1 have a factor
in the covering set
{3, 5, 7, 13, 19, 37, 73}. For another known Sierpinski number, 271129, the covering set is {3, 5, 7, 13, 17, 241}. All currently known Sierpinski numbers possess similar covering sets.
In 1967, Sierpiński and Selfridge conjecture
d 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, for every odd k below 78,557 there exists a positive integer n such that k2n+1 is prime. , there are only six candidates:
which have not been eliminated as possible Sierpinski numbers. Seventeen or Bust
(with PrimeGrid
), a distributed computing
project, is testing these remaining numbers. If the project finds a prime of the form k2n+1 for every remaining k, the Sierpinski problem will be solved.
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, a Sierpinski or Sierpiński number is an odd natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
k such that k2n + 1 is composite
Composite number
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
, for all natural numbers n; in 1960, Wacław Sierpiński proved that there are infinitely many odd integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s k which have this property.
In other words, when k is a Sierpinski number, all members of the following set are composite:
Numbers in this set with odd k and k < 2n are called Proth numbers.
Known Sierpinski numbers
The sequence of currently known Sierpinski numbers begins with:- 78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909, 965431, … .
The number 78,557 was proved to be a Sierpinski number by John Selfridge in 1962, who showed that all numbers of the form 78557·2n+1 have a factor
Factorization
In mathematics, factorization or factoring is the decomposition of an object into a product of other objects, or factors, which when multiplied together give the original...
in the covering set
Covering set
In mathematics, a covering set for a sequence of integers refers to a set of prime numbers such that every term in the sequence is divisible by at least one member of the set...
{3, 5, 7, 13, 19, 37, 73}. For another known Sierpinski number, 271129, the covering set is {3, 5, 7, 13, 17, 241}. All currently known Sierpinski numbers possess similar covering sets.
The Sierpinski problem
The Sierpinski problem is: "What is the smallest Sierpinski number?"In 1967, Sierpiński and Selfridge conjecture
Conjecture
A conjecture is a proposition that is unproven but is thought to be true and has not been disproven. Karl Popper pioneered the use of the term "conjecture" in scientific philosophy. Conjecture is contrasted by hypothesis , which is a testable statement based on accepted grounds...
d 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, for every odd k below 78,557 there exists a positive integer n such that k2n+1 is prime. , there are only six candidates:
- k = 10223, 21181, 22699, 24737, 55459, and 67607
which have not been eliminated as possible Sierpinski numbers. Seventeen or Bust
Seventeen or Bust
Seventeen or Bust is a distributed computing project started in March 2002 to solve the last seventeen cases in the Sierpinski problem.-Goals:...
(with PrimeGrid
PrimeGrid
PrimeGrid is a distributed computing project for searching for prime numbers of world-record size. It makes use of the Berkeley Open Infrastructure for Network Computing platform...
), a distributed computing
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
project, is testing these remaining numbers. If the project finds a prime of the form k2n+1 for every remaining k, the Sierpinski problem will be solved.
External links
- The Sierpinski problem: definition and status
- The Prime Sierpinski Problem, a related question.