Sierpinski number

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 integers k which have this property.

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

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

Numbers in such a set with odd k and k < 2n are Proth numbers.

Known Sierpiński numbers[edit]

The sequence of currently known Sierpiński numbers begins with:

78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909, 965431, … (sequence A076336 in OEIS).

The number 78557 was proved to be a Sierpiński 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 Sierpiński number, 271129, the covering set is {3, 5, 7, 13, 17, 241}. All currently known Sierpiński numbers possess similar covering sets.[1]

The Sierpiński problem[edit]

Further information: Seventeen or Bust
List of unsolved problems in mathematics
Is 78,557 the smallest Sierpiński number?

The Sierpiński problem is: "What is the smallest Sierpiński number?"

In 1967, Sierpiński and Selfridge conjectured that 78,557 is the smallest Sierpiński number, and thus the answer to the Sierpiński problem.

To show that 78,557 really is the smallest Sierpiński number, one must show that all the odd numbers smaller than 78,557 are not Sierpiński numbers. That is, for every odd k below 78,557 there exists a positive integer n such that k2n+1 is prime.[1] As of December 2013, there are only six candidates:

k = 10223, 21181, 22699, 24737, 55459, and 67607

which have not been eliminated as possible Sierpiński numbers.[2] 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 Sierpiński problem will be solved.

The smallest n for which k×2n+1 is prime[edit]

(sequence A040076 in OEIS)

k Smallest n
1 0
2 0
3 1
4 0
5 1
6 0
7 2
8 1
9 1
10 0
11 1
12 0
13 2
14 1
15 1
16 0
17 3
18 0
19 6
20 1
21 1
22 0
23 1
24 2
25 2
26 1
27 2
28 0
29 1
30 0
31 8
32 3
33 1
34 2
35 1
36 0
37 2
38 5
... ...
47 583
... ...
59 5
... ...
91 8
92 7
... ...
103 16
... ...
143 53
... ...
164 9
... ...
197 15
... ...
203 13
... ...
211 20
... ...
217 66
... ...
227 11
... ...
241 36
... ...
257 279
... ...
259 38
... ...
383 6393
... ...
2897 9715
... ...
3061 33288
... ...
4847 3321063
... ...
5297 50011
... ...
5359 5054502
... ...
7013 126113
... ...
7352 1839
... ...
8423 55157
... ...
10223 Unknown
... ...
19249 13018586
... ...
21181 Unknown
... ...
22699 Unknown
... ...
24737 Unknown
... ...
25819 111842
... ...
27653 9167433
... ...
27923 158625
... ...
28433 7830457
... ...
33661 7031232
... ...
39781 176088
... ...
44131 995972
... ...
46157 698207
... ...
54767 1337287
... ...
55459 Unknown
... ...
60541 176340
... ...
65567 1013803
... ...
67607 Unknown
... ...
69109 1157446
... ...
78557 None
... ...
79309 Unknown
... ...
79817 Unknown
... ...
90527 9162167
... ...
91549 Unknown
... ...
94373 3206717
... ...
98749 1045226
... ...
99739 Unknown
... ...
107929 1007898
... ...
123287 2538167
... ...
131072 Unknown
... ...
131179 Unknown
... ...
147559 2562218
... ...
149183 1666957
... ...
152267 Unknown
... ...
154801 1305084
... ...
156511 Unknown
... ...
157114 None
... ...
161041 Unknown
... ...
161957 727995
... ...
163187 Unknown
... ...
168451 Unknown
... ...
193997 Unknown
... ...
198677 2950515
... ...
200749 Unknown
... ...
202705 Unknown
... ...
209611 Unknown
... ...
211195 3224974
... ...
214519 1929114
... ...
216751 903792
... ...
219259 1300450
... ...
222113 Unknown
... ...
222361 2854840
... ...
225931 Unknown
... ...
227723 Unknown
... ...
229673 Unknown
... ...
237019 Unknown
... ...
238411 Unknown
... ...
241489 1365062
... ...
250463 1316921
... ...
258317 5450519
... ...
265711 4858008
... ...
271129 None
... ...

The first three "None" are conjectured on k = 78557, 157114 and 271129.

Note that all k ≤ 200 with n ≤ 8 except while k = 47, 94, 103, 143, 164, 188, and 197.

For more terms k ≤ 1200, see [1] (k≤300), [2] (301≤k≤600), [3] (601≤k≤900), and [4] (901≤k≤1200).

See also[edit]

References[edit]

Further reading[edit]

External links[edit]