Sierpinski number

From Infogalactic: the planetary knowledge core
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

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

<templatestyles src="Module:Hatnote/styles.css"></templatestyles>

Question dropshade.png Open problem in mathematics:
Is 78,557 the smallest Sierpiński number?
(more open problems in mathematics)

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, there is also a second Sierpinski number search project. The unknown values of k between 78557 and 271129 are

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

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

0, 0, 1, 0, 1, 0, 2, 1, 1, 0, 1, 0, 2, 1, 1, 0, 3, 0, 6, 1, 1, 0, 1, 2, 2, 1, 2, 0, 1, 0, 8, 3, 1, 2, 1, 0, 2, 5, 1, 0, 1, 0, 2, 1, 2, 0, 583, 1, 2, 1, 1, 0, 1, 1, 4, 1, 2, 0, 5, 0, 4, 7, 1, 2, 1, 0, 2, 1, 1, 0, 3, 0, 2, 1, 1, ... (sequence A040076 in OEIS) or OEISA078680 (not allow that n = 0), for odd ks, see OEISA046067 or OEISA033809 (not allow that n = 0).

The first three k such that the kth term of this sequence is not defined are conjectured to be 78557, 157114 and 271129.

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

Simultaneously Sierpiński and Riesel

A number may be simultaneously Sierpiński and Riesel. These are called Brier numbers. The smallest five known examples are 3316923598096294713661, 10439679896374780276373, 11615103277955704975673, 12607110588854501953787, 17855036657007596110949, ... (A076335).[3]

The dual Sierpinski problem

A dual Sierpinski number is defined as an odd natural number k such that 2n + k is composite for all natural numbers n. There is a conjecture that the set of these numbers is the same as the set of Sierpinski numbers; for example, 2n + 78557 is composite for all natural numbers n, and 78557 was proven to be the smallest dual Sierpinski 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 Sierpinski 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 k < 78557, so it is currently known that 78557 is the smallest dual Sierpinski number.

The Sierpinski 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 2n + k, or the dual Sierpinski 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 | 2n − (−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 n 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.

n \ k positive negative positive (allow even k) negative (allow even k)
positive OEISA033809 OEISA108129 OEISA078680 OEISA050412
negative OEISA067760 OEISA252168 - -
positive (or 0) OEISA046067 OEISA046069 OEISA040076 OEISA040081
negative (with condition: 2-n > -k) - OEISA096502 - -

Sierpinski number base b

A Sierpinski number in base b is a natural number k such that gcd(k+1, b−1) = 1 and k×bn + 1 is composite for all natural number n > 0.[4][5][6]

b Conjectured smallest Sierpinski k cover set / algebraic factors remaining k with no known primes Largest prime found
2 78557 {3, 5, 7, 13, 19, 37, 73} 10223, 20446, 21181, 22699, 24737, 40892, 42362, 45398, 49474, 55459, 65536, 67607 19249×213018586+1
3 125050976086 {5, 7, 13, 17, 19, 37, 41, 193, 757} 6363484, 8911036, 12663902, 14138648, 14922034, 18302632, 19090452, 21497746, 23896396, 24019448, 24677704, 26733108, ... 98392246×3494564+1
4 66741 {5, 7, 13, 17, 241} 18534, 20446, 21181, 22699, 49474, 55459, 64494, 65536 19249×46509293+1
5 159986 {3, 7, 13, 31, 601} 6436, 7528, 10918, 26798, 29914, 31712, 32180, 36412, 37640, 41738, 44348, 44738, 45748, 51208, 54590, 58642, 60394, 62698, 64258, 67612, 67748, 71492, 74632, 76724, 77072, 81556, 83936, 84284, 90056, 92158, 92906, 93484, 105464, 118568, 126134, 133990, 138514, 139196, 149570, 152588, 154222, 158560 144052×52018290+1
6 174308 {7, 13, 31, 37, 97} 1296, 7776, 13215, 14505, 46656, 50252, 76441, 79290, 87030, 87800, 97131, 112783, 124125, 127688, 166753, 168610 139413×61279992+1
7 1112646039348 {5, 13, 19, 43, 73, 181, 193, 1201} 987144, 1613796, 1911142, 2052426, 2471044, 3778846, 4023946, 4300896, 4369704, 4455408, 4723986, 4783794, 4810884, ... 1952376×7293352+1
8 1 1×8n + 1 = (1×2n + 1) × (1×4n − 1×2n + 1) none (proven) (none)
9 2344 {5, 7, 13, 73} 2036 1846×965376+1
10 9175 {7, 11, 13, 37} 100, 1000, 7666 5028×1083982+1
11 1490 {3, 7, 19, 37} none (proven) 958×11300544+1
12 521 {5, 13, 29} 12, 144 404×12714558+1
13 132 {5, 7, 17} none (proven) 48×136267+1
14 4 {3, 5} none (proven) 3×141+1
15 91218919470156 {13, 17, 113, 211, 241, 1489, 3877} 215432, 424074, 685812, 734268, 1868998, 1936420, ... 4713672×1583962+1
16 2500 2500×16n + 1 = (50×4n − 10×2n + 1) × (50×4n + 10×2n + 1) none (proven) 186×165229+1
17 278 {3, 5, 29} 244 262×17186768+1
18 398 {5, 13, 19} 18, 324 122×18292318+1
19 765174 {5, 7, 13, 127, 769} 1446, 2526, 2716, 3714, 4506, 4614, 6796, 10776, 14556, 15394, 15396, 15616, 16246, 17596, 19014, 19906, 20326, 20364, 21696, 24754, 25474, 27474, 29746, 29896, 29956, 30196, 36534, 38356, 39126, 39276, 42934, 43986, 44106, 45216, 45846, 46174, 47994, ... 564544×19145165+1
20 8 {3, 7} none (proven) 6×2015+1
21 1002 {11, 13, 17} none (proven) 118×2119849+1
22 6694 {5, 23, 97} 22, 484, 5128 1611×22738988+1
23 182 {3, 5, 53} none (proven) 68×23365239+1
24 30651 {5, 7, 13, 73, 79} 656, 1099, 1851, 1864, 2164, 2351, 2586, 3051, 3404, 3526, 3609, 3706, 3846, 4606, 4894, 5129, 5316, 5324, 5386, 5889, 5974, 6181, 7276, 7394, 7481, 7746, 7789, 7844, 8054, 8091, 8161, 8369, 8684, 9279, 9304, 9621, 9701, 9721, 9726, ... 4799×2499451+1
25 262638 {7, 13, 31, 601} 222, 5550, 6436, 7528, 10918, 12864, 13548, 15588, 18576, 29914, 35970, 36412, 45330, 45748, ... 144052×251009145+1
26 221 {3, 7, 19, 37} 65, 155 32×26318071+1
27 8 8×27n + 1 = (2×3n + 1) × (4×9n − 2×3n + 1) none (proven) 2×272+1
28 4554 {5, 29, 157} 871, 4552 3394×28427262+1
29 4 {3, 5} none (proven) 2×291+1
30 867 {7, 13, 19, 31} 278, 588 699×3011837+1

Conjectured smallest Sierpinski number in base n are

78557, 125050976086, 66741, 159986, 174308, 1112646039348, 1, 2344, 9175, 1490, 521, 132, 4, 91218919470156, 2500, 278, 398, 765174, 8, 1002, 6694, 182, 30651, 262638, 221, 8, 4554, 4, 867, 6360528, 1, 1854, 6, 214018, 1886, 2604, 14, 166134, 826477, 8, 13372, 2256, 4, 53474, 14992, 8, 1219, 2944, 16, ... (sequence A123159 in OEIS)

See also

References

Further reading

  • Lua error in package.lua at line 80: module 'strict' not found.

External links