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.

Since the second proved Siepinski number is 271129, the unknown values of k between 78557 and 271129 are

79309, 79817, 91549, 99739, 131179, 152267, 156511, 161041, 163187, 168451, 193997, 200749, 202705, 209611, 222113, 225931, 227723, 229673, 237019, 238411

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

(sequence A040076 in OEIS) or OEISA078680 (not allow that n = 0), for odd ks, see OEISA046067 or OEISA033809 (not allow that n = 0).

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).

The dual Siepinski problem[edit]

The dual Siepinski numbers are defined as an odd natural number k such that 2n + k is composite for all natural number n, there is a conjecture that the set of this numbers is the same as the set of Siepinski numbers, for example, 2n + 78557 is composite for all natural number n, and 78557 was proven to be the smallest dual Siepinski number.

The least n such that 2n + k is prime are (for odd ks)

1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 3, 2, 1, 1, 4, 2, 1, 2, 1, 1, 2, 1, 5, 2, 1, 3, 2, 1, 1, 8, 2, 1, 2, 1, 1, 4, 2, 1, 2, 1, 7, 2, 1, 3, 4, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 7, 4, 5, 3, 4, 2, 1, 2, 1, 3, 2, 1, 1, 10, 3, 3, 2, 1, 1, ... (sequence A067760 in OEIS)

There are no unknown terms below 78557, so 78557 is proved to be the smallest dual Siepinski number. However, some values of ns are large, for example, the smallest solution for that k = 2131, 40291, and 41693, the least n are 4583176, 9092392, and 5146295. (However, the least n such that k2n + 1 is only 44, 8, and 33. Interestingly, the least n which 2n + 10223 is prime is only 19.)

The odd ks which 2n + k are composite for all n < k are

773, 2131, 2491, 4471, 5101, 7013, 8543, 10711, 14717, 17659, 19081, 19249, 20273, 21661, 22193, 26213, 28433, ... (sequence A033919 in OEIS)

There is also a "five or bust", similar to seventeen or bust, considers this problem, and found primes for all ks < 78557, so it is currently known that 78557 is the smallest dual Siepinski number.

The Siepinski function is k2n + 1, in fact, it can be also defined for all odd integer k and all integer n (n does not equal to 0), both of them can be either positive or negative; if we let n negative, the function will become \frac{2^{-n} + k}{2^{-n}}, if we choose the numerator of it, it will be 2-n + k, or the dual Siepinski function; if we let k negative, the function will become -((-k)2n - 1), if we choose the absolute of it, it will be (-k)2n - 1, or the Riesel function; if we let both k and n negative, the function will become -\frac{2^{-n} - (-k)}{2^{-n}}, if we choose the absolute of the numerator of it, it will be |2-n - (-k)|, or the dual Riesel function, so we can define a function \Xi(k, n) = abs(numerator(k2^n+1)) for all odd integer k and all integer n (n does not equal to 0), both of them can be either positive or negative, and we can find all ns which \Xi(k, n) is prime for an odd integer k. However, there is still no primes for which k = 78557, 271129, -509203, etc. There is a conjecture that all such numbers have a covering set, but it is false to some perfect power numbers, and there is still a conjecture that all such numbers which are not perfect power numbers have a covering set.

See also[edit]

References[edit]

Further reading[edit]

External links[edit]