Searching for large Sierpinski numbers

In this article's immediate predecessor, I described the results of a survey of Sierpinski numbers, which consisted mainly of enumerating these to a limit of 5*108 and highlighting any issues that were raised along the way. In the current article, rather than build up data gradually, I will take a more global view of the results and matters arising from a survey to the extended limit of 2*109.

The search method is as before, where each possible value of k, not divisible by 3, 5 or 7, is tested for each exponent n from 1 to 1000. If any prime is found for a particular k, that value of k is ignored. All values of k which survive this step are then passed to the program psieve3.exe, which builds up a list of Nash congruences. If at any time, the accumulation of Nash congruences combine to produce a complete covering, then we have a Sierpinski number, and the associated covering set can be extracted from the congruences (though not without the occasional difficulty). Covering sets are labelled, generally according to the order they were first identified.

The complete list of covering sets associated with at least one Sierpinski number under 2*109 is as follows (where P is the product of the primes in the set):

 code modulus covering set 2P A 24 {3, 5, 7, 13, 17, 241} 1.1e7 B 36 {3, 5, 7, 13, 19, 37, 73} 1.4e8 C 48 {3, 5, 7, 13, 17, 97, 257} 1.1e9 D 36 {3, 5, 7, 13, 19, 73, 109} 4.1e8 E 36 {3, 5, 7, 13, 19, 37, 109} 2.1e8 F 36 {3, 5, 7, 13, 37, 73, 109} 8.0e8 G 72 {3, 5, 7, 13, 17, 19, 109, 433} 4.2e10 H 48 {3, 5, 7, 17, 97, 241, 257} 2.2e10 I 48 {3, 5, 7, 13, 17, 257, 673} 8.0e9 K 72 {3, 5, 7, 13, 17, 19, 37, 433} 1.4e10 L 48 {3, 5, 7, 13, 17, 97, 673} 3.0e9 M 48 {3, 5, 13, 17, 97, 241, 257} 4.0e10 N 72 {3, 5, 7, 17, 19, 37, 109, 241} 6.6e10 P 72 {3, 5, 7, 17, 19, 37, 73, 241} 4.4e10 R 72 {3, 5, 7, 13, 17, 37, 109, 433} 8.1e10 S 72 {3, 5, 7, 13, 17, 19, 73, 433} 2.8e10 T 60 {3, 5, 7, 11, 13, 41, 61, 151, 331} 3.8e12 U 60 {3, 5, 7, 11, 13, 31, 41, 61, 331} 7.7e11 V 72 {3, 5, 7, 17, 37, 109, 241, 433} 1.5e12 W 72 {3, 5, 7, 13, 19, 109, 241, 433} 5.9e11 X 60 {3, 5, 7, 11, 13, 31, 41, 61, 151} 3.5e11 Y 48 {3, 5, 7, 13, 97, 241, 673} 4.3e10 Z 72 {3, 5, 13, 17, 19, 37, 109, 241} 1.2e11 AA 48 {3, 5, 7, 17, 97, 257, 673} 6.0e10 AB 48 {3, 5, 13, 17, 97, 241, 673} 1.0e11 AC 72 {3, 5, 7, 13, 19, 37, 241, 433} 2.0e11 AD 72 {3, 5, 7, 13, 37, 73, 241, 433} 7.7e11 AE 144 {3, 5, 7, 13, 17, 19, 73, 97, 577} 3.6e12 AF 72 {3, 5, 7, 17, 19, 73, 109, 241} 1.3e11 AG 72 {3, 5, 7, 13, 17, 37, 73, 433} 5.4e10 AH 144 {3, 5, 7, 13, 17, 19, 73, 257, 577} 9.5e12 AI 72 {3, 5, 7, 13, 17, 73, 109, 433} 1.6e11 AJ 48 {3, 5, 7, 13, 97, 241, 257} 1.6e10 AK 72 {3, 5, 7, 17, 37, 73, 109, 241} 2.5e11 AL 72 {3, 5, 7, 13, 19, 73, 241, 433} 4.0e11 AM 72 {3, 5, 7, 17, 19, 37, 241, 433} 2.6e11 AN 60 {3, 5, 7, 11, 13, 31, 41, 61, 1321} 3.1e12 AP 48 {3, 5, 7, 17, 241, 257, 673} 1.5e11 AR 60 {3, 5, 7, 13, 31, 41, 61, 151, 331} 1.1e13 AS 72 {3, 5, 13, 17, 19, 73, 109, 241} 2.4e11 AT 180 {3, 5, 7, 11, 13, 19, 37, 61, 151, 181, 631} 2.2e16 AU 72 {3, 5, 13, 17, 19, 37, 73, 241} 8.2e10 AV 48 {3, 5, 7, 17, 97, 241, 673} 5.6e10 AW 60 {3, 5, 7, 11, 13, 31, 61, 151, 1321} 1.1e13 AX 72 {3, 5, 7, 17, 19, 73, 241, 433} 5.2e11 AY 144 {3, 5, 7, 17, 37, 73, 97, 109, 257} 2.6e13 AZ 72 {3, 5, 13, 17, 37, 73, 109, 241} 4.7e11 BA 48 {3, 5, 13, 17, 97, 257, 673} 1.1e11 BB 180 {3, 5, 7, 11, 13, 19, 31, 41, 73, 181, 631} 6.0e15 BC 60 {3, 5, 7, 11, 13, 31, 41, 151, 331} 1.9e12

The letter J is missing from this list for historical reasons, as it was once used to explain the concept of overlaps (Sierpinski numbers belonging to more than one Keller cycle).

The above list includes 12 of the 15 available covering sets of modulus 48, but surprisingly only 7 of the 23 available covering sets of modulus 60. No Sierpinski numbers of modulus 96 occur within the current limit.

The Keller cycle produced by the Keller iteration k ® (2k+P) mod 2P (where P is the product of the primes in the covering set) is a closed loop of length equal to the modulus of the covering set.

For a given covering set, once the 2P limit is reached, there can be no more Keller cycles and so the number of these is finite. Additionally, the concept of the flip cycle has already been introduced. Amongst other things, this guarantees that for any covering set whose constituent primes have order modulo 2 that are not all even or not all odd, there must be an even number of Keller cycles. To the current search limit of 109, this has been verified to be true for covering sets A, B, C, D, E and F.

The current allocation of covering sets to Keller cycles is as follows:

 set modulus # cycles status A 24 2 (complete) B 36 4 (complete) C 48 2 (complete) D 36 4 (complete) E 36 4 (complete) F 36 4 (complete) G 72 4 H 48 2 I 48 2 K 72 4 L 48 2 M 48 2 N 72 3 P 72 4 R 72 3 S 72 4 T 60 2 U 60 2 V 72 1 W 72 1 X 60 12 Y 48 2 Z 72 2 AA 48 2 AB 48 1 AC 72 2 AD 72 1 AE 144 1 AF 72 3 AG 72 4 AH 144 1 AI 72 1 AJ 48 2 AK 72 2 AL 72 2 AM 72 2 AN 60 4 AP 48 1 AR 60 1 AS 72 1 AT 180 1 AU 72 1 AV 48 1 AW 60 2 AX 72 1 AY 144 1 AZ 72 1 BA 48 1 BB 180 1 BC 60 1 114

I have no explanation as yet for the high incidence of cycles with covering set X.

There are 13394 distinct Sierpinski numbers in the range considered, including 141 overlaps.

This includes only four values, namely 308914459, 1319709979, 1554424697 and 1905955429 that are divisible by 7.

The smallest Sierpinski numbers for each of the moduli identified so far are:

 modulus smallest Sierpinski number 24 271129 36 78557 48 327739 60 169073869 72 1777613 144 516108143 180 1143502909

One value, namely 987152869, is the base value for two distinct Keller cycles, both of modulus 60. This is the only occurrence of such in the range considered.

My previous numbering of Keller cycles was based on the order in which they were found. However, the cases of the Sierpinski number divisible by 7, and the increasing number of overlaps, sometimes means that in order to retain a rising sequence, some re-ordering has to take place every now and then. To avoid this, I have simply listed the base values in increasing order.

The full list of Keller cycle base values, with associated covering sets, is as follows:

 sequence base number modulus covering set factorisation 1 78557 36 B 17*4621 2 271129 24 A prime 3 271577 24 A 59*4603 4 322523 36 F prime 5 327739 48 C prime 6 934909 36 D prime 7 1290677 36 E 137*9421 8 1777613 72 G 29*61297 9 2510177 36 B 167*15031 10 5455789 48 C 59*89*1039 11 5841947 36 E 271*21557 12 6828631 36 D 23*337*881 13 8184977 36 B prime 14 8959163 36 E prime 15 10306187 36 E prime 16 11206501 48 H prime 17 11822359 36 D prime 18 12413281 36 F 17*191*3823 19 12756019 36 B prime 20 15273751 48 I prime 21 17220887 36 D 3709*4643 22 22024609 72 K 1303*16903 23 24885199 48 L 113*191*1153 24 27862127 36 F 29*960763 25 36029731 72 G 71*507461 26 37158601 48 M prime 27 41134369 48 L prime 28 51612259 72 N 149*346391 29 51889823 72 P 2347*22109 30 56191673 72 AU 79*711287 31 57816799 36 F 53*1090883 32 59198569 72 K prime 33 105885947 72 R 3181*33287 34 108628343 72 S 151*719393 35 115281169 72 K 311*370679 36 146053577 72 G 4721*30937 37 155223473 72 S 37*4195229 38 156701453 72 P 3931*39863 39 169073869 60 T 53*163*19571 40 174329011 60 U 59*257*11497 41 210465533 72 P 181*1162793 42 211062227 72 V prime 43 212497043 72 W 11*19317913 44 213578567 48 I 127*1681721 45 240936503 72 K 1129*213407 46 266142407 60 X 23*347*33347 47 278770729 48 Y 2551*109279 48 292099127 60 X 37*2659*2969 49 297988073 60 X prime 50 308914459 72 Z 7*41*101*10657 51 332320309 60 X 292*73*5413 52 341371831 48 AA 2711*125921 53 359292259 48 AB 131*2742689 54 365928503 72 AC 347*1054549 55 369699767 72 R 43*8597669 56 389737669 48 AP prime 57 478078081 48 AA 13*412*131*167 58 482420221 72 G 71*6794651 59 488303521 60 X prime 60 497369479 60 X 19*683*38327 61 510877279 72 AD 11*79*587891 62 516108143 144 AE prime 63 563461069 72 AF 97*1051*5527 64 577256123 72 AG 43*13424561 65 597875869 48 H 19*23*1031*1327 66 605248493 144 AH 2351*257443 67 613997417 48 AJ 11*673*82939 68 615884447 72 P 1523*404389 69 620629981 72 AI 3461*179321 70 627253343 72 N prime 71 689546903 72 AK 277*2489339 72 693557633 72 AL 211*3287003 73 710530043 60 X 7507*94649 74 757599167 72 N 13*58276859 75 764612281 48 AJ 17*557*80749 76 769883761 72 S 23*5449*6143 77 832047023 72 R 17047*48809 78 839316707 60 X 17*1109*44519 79 844627607 72 AM 1901*444307 80 879092101 48 Y 1109*792689 81 914079949 60 AN 19*3491*13781 82 974552641 60 AN 151*379*17029 83 987152869 60 U 337*2929397 84 987152869 60 AR 337*2929397 85 1017439067 48 M 41*24815587 86 1021957141 72 AS prime 87 1038777953 72 S prime 88 1051180381 72 AG prime 89 1077331111 60 AN prime 90 1077974903 60 AN 6637*162419 91 1088472887 72 AZ 59*199*92707 92 1143502909 180 AT 17*239*431*653 93 1156418821 60 X 59*19600319 94 1161643607 72 AG 439*2646113 95 1181603461 72 AG 107*929*11887 96 1269436171 48 AV 23*55192877 97 1316626321 60 T 73*18035977 98 1329539273 72 AM 35461*37493 99 1366677863 72 Z 20269*76427 100 1373855461 72 AC 11*43*2904557 101 1452979757 60 AW prime 102 1460644561 60 X prime 103 1471655687 72 AL 79*193*263*367 104 1502556901 72 AX 101*14876801 105 1550990453 72 AF 61*4967*5119 106 1591804639 60 X 17*37*73*34667 107 1642059527 72 AK prime 108 1644987931 72 AF 499*3296569 109 1695587059 144 AY prime 110 1828217513 60 X 677*2700469 111 1840951877 48 BA 2467*746231 112 1850694047 180 BB prime 113 1945610987 60 BC prime 114 1946251501 60 AW prime

Sometimes because of an overlap, a non-base value is identifed before a base value for certain Keller cycles. This explains the occasional inconsistency in the labelling of covering sets (e.g. AJ before AI, the positioning of AP, etc.).

I have created a comprehensive list of every Sierpinski number to the limit of 109. In this list, individual Sierpinski numbers are labelled according to their position in the associated Keller cycle, with base (or smallest) values given an index of 0. Generated values, that is, Sierpinski numbers obtained by using the open iteration k ® (k+2P) are not individually labelled, but simply identified by the code of their covering set.