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 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:

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 the 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]

Sierpiński problem[edit]

Further information: Seventeen or Bust
Question dropshade.png Unsolved problem in mathematics:
Is 78,557 the smallest Sierpiński number?
(more unsolved 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 Sierpiński number is 271129, there is also a second Sierpiński 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

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

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 the 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[edit]

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]

Dual Sierpinski problem[edit]

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.

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 the OEIS)

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 the OEIS)

There is also a "five or bust", similar to seventeen or bust, considers this problem, and found (probable) primes for all k < 78557 (the largest prime is 29092392 + 40291[4]), so it is currently known that 78557 is the smallest dual Sierpinski number.

Sierpinski number base b[edit]

One can generalize the Sierpinski problem to an integer base b ≥ 2. A Sierpinski number base b is a positive integer k such that gcd(k + 1, b − 1) = 1 (if gcd(k + 1, b − 1) > 1, then there is a prime p divides gcd(k + 1, b − 1), so p divides both k + 1 and b − 1. Thus, p divides k×bn + 1 for all positive integer n, so k×bn + 1 has a trivial prime factor of p. Thus, we don't consider this situation) and k×bn + 1 is not prime for all positive integer n.[5][6][7] For every integer b ≥ 2, there are infinitely many Sierpinski numbers base b. For example, all numbers congruent to 174308 mod 10124569 and not congruent to 4 mod 5 are Sierpinski numbers base 6. We want to find and prove the smallest Sierpinski number base b for every integer b ≥ 2. It is a conjecture that if k is a Sierpinski number base b, then at least one of the three conditions holds:

  1. All numbers of the form k×bn + 1 have a factor in some covering set. (For example, b = 22, k = 6694, then all numbers of the form k×bn + 1 have a factor in the covering set: {5, 23, 97})
  2. k×bn + 1 has algebraic factors. (For example, b = 16, k = 2500, then k×bn + 1 can be factored to (50×4n − 10×2n + 1) × (50×4n + 10×2n + 1))
  3. For some n, numbers of the form k×bn + 1 have a factor in some covering set; and for all other n, k×bn + 1 has algebraic factors. (For example, b = 55, k = 2500, then if n is not divisible by 4, then all numbers of the form k×bn + 1 have a factor in the covering set: {7, 17}, if n is divisible by 4, then k×bn + 1 can be factored to (50×55n/2 − 10×55n/4 + 1) × (50×55n/2 + 10×55n/4 + 1))

There is a special and interesting counterexample: b = 128, k = 8 (8 is not the smallest Sierpinski number base 128, the smallest Sierpinski number base 128 is 1 since 1×128n + 1 = (1×2n + 1) × (1×64n − 1×32n + 1×16n − 1×8n + 1×4n − 1×2n + 1), it has algebraic factors). Since 8×128n + 1 = 27n+3 + 1, and if 2r + 1 is prime, then r must be a power of 2, but 7n+3 cannot be a power of 2 since all powers of 2 are congruent to 1, 2, or 4 (mod 7), so all numbers of the form 8×128n + 1 are composite. Thus, 8 is a Sierpinski number base 128 since 8+1 and 128−1 are coprime. However, there is no covering set for 8×128n + 1 since if so, then we find the orders of 2 to mod all the primes in the covering set and find the exponents of highest power of 2 dividing the orders, and choose r greater than the largest exponent, since for every natural number r, there is a n such that 2r divides 7n+3, so no prime in the covering set divide 27n+3 (since if so, then the order of 2 to mod the prime is divisible by 2r, but according above, the order of 2 to mod all primes in the covering set is not divisible by 2r). Besides, 8×128n + 1 has no algebraic factors since there is no odd r > 1 such that both 128 and 8 are perfect rth powers, and 128 is not a perfect fourth power. Thus, this conjecture is not completely true, but it may be true except when b = ar and k = as with even positive integer a not of the form mt with integer m and odd integer t > 1, positive integer r and nonnegative integer s, gcd(r, s) = largest power of 2 dividing r, and 2xs (mod r) has no solution.

In the following list, we only consider those positive integers k such that gcd(k + 1, b − 1) = 1, and all n must be ≥ 1.

Note: k-values that are a multiple of b and where k+1 is not prime are included in the conjectures (and included in the remaining k with red color if no primes are known for these k-values) but excluded from testing (Thus, never be the k of "largest 3 primes found"), since such k-values will have the same prime as k / b.

b conjectured smallest Sierpinski k covering set / algebraic factors remaining k with no known primes largest 3 primes 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
27653×29167433+1
28433×27830457+1
3 125050976086 {5, 7, 13, 17, 19, 37, 41, 193, 757} 6363484, 8911036, 12663902, 14138648, 14922034, 18302632, 19090452, 21497746, 23896396, 24019448, 24677704, 26733108, 33224138, 33381178, 35821276, 37063498, 37991706, 39431872, 42415944, 44766102, 46891088, 47628292, 54503602, 54907896, 56882284, 57271356, 60581468, 61270336, 63362504, 64493238, 69487006, 70143826, 70258712, 71689188, 72058344, 73440644, 74033112, 76020188, 77475694, 77574956, 78703468, 80199324, 81095362, 82085494, 88091054, 93455522, 96103394, 97696726, 99613186, 99672414, ... 608558012×3498094+1
961852454×3495371+1
98392246×3494564+1
4 66741 {5, 7, 13, 17, 241} 18534, 20446, 21181, 22699, 49474, 55459, 64494, 65536 19249×46509293+1
55306×44583716+1
56866×43915228+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, 81556, 83936, 84284, 90056, 92906, 93484, 105464, 118568, 126134, 133990, 138514, 139196, 149570, 152588, 158560 92158×52145024+1
77072×52139921+1
154222×52091432+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
33706×6910462+1
125098×6896696+1
7 1112646039348 {5, 13, 19, 43, 73, 181, 193, 1201} 987144, 1613796, 1911142, 2052426, 2471044, 3778846, 4023946, 4300896, 4369704, 4455408, 4723986, 4783794, 4810884, 6551056, 6910008, 7115518, 7248984, 8186656, 8566504, 9230674, 9284172, 9566736, ... 1952376×7293352+1
5452324×7277094+1
5071026×7261921+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
1804×944103+1
1884×916093+1
10 9175 {7, 11, 13, 37} 100, 1000, 7666 5028×1083982+1
7404×1044826+1
8194×1021129+1
11 1490 {3, 7, 19, 37} none (proven) 958×11300544+1
1468×1126258+1
416×1112741+1
12 521 {5, 13, 29} 12, 144 404×12714558+1
378×122388+1
261×12644+1
13 132 {5, 7, 17} none (proven) 48×136267+1
120×131552+1
106×1356+1
14 4 {3, 5} none (proven) 1×142+1
3×141+1
2×141+1
15 91218919470156 {13, 17, 113, 211, 241, 1489, 3877} 215432, 424074, 685812, 734268, 1868998, 1936420, 2831648, 3100818, 3231480, 3789018, 3859132, ... 4713672×1583962+1
3429436×1578867+1
4149714×1572183+1
16 2500 2500×16n + 1 = (50×4n − 10×2n + 1) × (50×4n + 10×2n + 1) none (proven) 2158×1610905+1
186×165229+1
798×162181+1
17 278 {3, 5, 29} 244 262×17186768+1
160×17166048+1
92×1751311+1
18 398 {5, 13, 19} 18, 324 122×18292318+1
381×1824108+1
291×182415+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, 50124, 51604, 53014, 55516, 57544, 59214, 60874, 61536, 63766, 64426, 64654, 64686, 64956, 66316, 67054, 68136, 69114, 70566, 72384, 72774, 73824, 76326, 77764, 79594, 80856, 80914, 81786, 83434, 84184, 84276, 84324, 85614, 85704, 86446, 86634, 87666, 87786, 87994, 90016, 90024, 92056, 95136, 96864, 98014, 99124, ... 110946×19157286+1
623184×19153769+1
749356×19152372+1
20 8 {3, 7} none (proven) 6×2015+1
7×202+1
4×202+1
21 1002 {11, 13, 17} none (proven) 118×2119849+1
922×21230+1
736×21215+1
22 6694 {5, 23, 97} 22, 484, 5128 1611×22738988+1
1908×22355313+1
4233×22304046+1
23 182 {3, 5, 53} none (proven) 68×23365239+1
8×23119215+1
122×2314049+1
24 30651 {5, 7, 13, 73, 79} 656, 1099, 1851, 1864, 2164, 2351, 2586, 3404, 3526, 3609, 3706, 3846, 4606, 4894, 5129, 5316, 5324, 5386, 5889, 5974, 7276, 7746, 7844, 8054, 8091, 8161, 8369, 9279, 9304, 9701, 9721, 10026, 10156, 10531, 11346, 12799, 12969, 12991, 13716, 13984, 15744, 15921, 17334, 17819, 17876, 18006, 18204, 18911, 19031, 19094, 20219, 20731, 21459, 21526, 22289, 22356, 22479, 23844, 23874, 23981, 24784, 25964, 26279, 26376, 26804, 27344, 28099, 28249, 29009, 29091, 29349, 29464, 29566, 29601, 29641 27611×24219946+1
29116×24216988+1
29619×24204203+1
25 262638 {7, 13, 31, 601} 222, 5550, 6436, 7528, 10918, 12864, 13548, 15588, 18576, 29914, 35970, 36412, 45330, 45748, 51208, 57240, 58434, 58642, 60394, 62698, 64258, 65610, 66678, 67612, 74632, 75666, 76896, 81186, 81556, 82962, 86334, 90240, 91038, 93378, 93484, 94212, ... 92158×251072512+1
154222×251045716+1
144052×251009145+1
26 221 {3, 7, 19, 37} 65, 155 32×26318071+1
217×2611454+1
95×261683+1
27 8 8×27n + 1 = (2×3n + 1) × (4×9n − 2×3n + 1) none (proven) 2×272+1
6×271+1
4×271+1
28 4554 {5, 29, 157} 871, 4552 3394×28427262+1
4233×28331135+1
2377×28104621+1
29 4 {3, 5} none (proven) 2×291+1
30 867 {7, 13, 19, 31} 278, 588 699×3011837+1
242×305064+1
659×304936+1
31 6360528 {7, 13, 19, 37, 331} 76848, 124812, 135682, 148260, 155140, 185778, 208008, 217608, 231096, 245200, 257206, 260662, 262842, 263328, 272410, 303628, 311566, 313650, 348262, 369370, 385978, 413706, 419470, 450178, 457090, 464608, 475266, 479038, 504990, 512518, 513850, 579630, 596916, 613456, 626176, 635188, 679542, 699676, 731128, 748726, 749416, 756192, 758568, 785110, 786232, 805470, 810930, 811078, 822918, 828856, 843246, 852370, 871356, 879126, 888850, 889992, 899802, 908296, 916648, 961032, 965238, 966820, 975300, 994746, 999598, ... 3419662×3197826+1
1751346×3197378+1
2983422×3197021+1
32 1 1×32n + 1 = (1×2n + 1) × (1×16n − 1×8n + 1×4n − 1×2n + 1) none (proven) (none)

Conjectured smallest Sierpinski number base n are (start with n = 2)

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, 5183582, 28674, 1966, 21, 2500, 20, 1188, 43071, 4, 16957, 15168, 8, 3511808, 1, ... (sequence A123159 in the OEIS)

See also[edit]

References[edit]

Further reading[edit]

External links[edit]