Searching for large Sierpinski numbers

overlaps

flip cycles

In an earlier article, I introduced a method for generating numbers which have a good chance of having a Nash weight of less than 100. A side-effect of this is of course the locating of Sierpinski numbers themselves, which have a Nash weight of zero. In fact the method may be modified specifically to find Sierpinski numbers, by ignoring k as soon as any value of n between 1 and 1000 survives the trial division, although in practice it is convenient to preserve the possibility of one or two exceptions. It takes only a few minutes to run this for all k up to one million, and it produces a list of 11 survivors, all of which, when run through the Nash sieve, are identified as Sierpinski numbers.

It is important to point out that for each k, the exponent n must be run to 1000. For example, if the modified algorithm is run for odd k between 70000 and 100000, and n only up to 100, then instead of leaving one possible candidate, there are 16 to be considered. Some of these, to be fair, have very low Nash weights, but only one (78557) has zero Nash weight.

It is possible that additional Sierpinski numbers are not identified because either

a) the Sierpinski number is divisible by 3, 5 or 7

or

b) a member of the covering set is greater than 6400 (the sieve limit).

As will become apparent, the dangers posed by condition a) are removed by the nature of certain relationships governing Sierpinski numbers. Also, there is a margin of error in the search algorithm that will cope with covering sets with one or two large primes.

The following list gives all Sierpinski numbers found using this method for k < 107. As a comparison, the algorithm was run for all k < 5.106 without the restriction that k is not divisible by 3, 5, or 7, and no other Sierpinski numbers were located. I am therefore confident that the number of Sierpinski numbers not identified in the range of k searched is very small and may, in fact, be zero.

The covering set for a Sierpinski number k is a subset of the divisors of 2s - 1 for some minimal value s. This number is given in the second column and is called the Sierpinski modulus for k. Covering sets themselves are letter-coded in the fourth column, as follows :

 code modulus covering set A 24 {3, 5, 7, 13, 17, 241} B 36 {3, 5, 7, 13, 19, 37, 73} C 48 {3, 5, 7, 13, 17, 97, 257} D 36 {3, 5, 7, 13, 19, 73, 109} E 36 {3, 5, 7, 13, 19, 37, 109} F 36 {3, 5, 7, 13, 37, 73, 109} G 72 {3, 5, 7, 13, 17, 19, 109, 433}

It is obvious that if k is a Sierpinski number and P is the product of the primes in the covering set for k, then all the numbers generated by the iteration k ® (2k+P) mod 2P are also Sierpinski numbers with the same covering set. This iterative process repeats with period equal to the Sierpinski modulus s of k and is known as the Keller iteration. The sequence of s repeating numbers so generated is called a Keller cycle. In the fifth column below we attempt to indicate this using the following code: proceeding sequentially, if a value of k has not been previously identified as being a member of a particular cycle, then it is given the code N.0 where N is a number that starts at 1 and is incremented every time a new cycle is identified. The Keller cycle is then generated and a member of the cycle is labelled N.i if it is the ith iteration of the cycle. We proceed in this manner until all the values of k are labelled. Note that N.0 = N.s, where s is the Sierpinski modulus.

For interest, the third column contains either the word "prime" if k is prime, or the prime factors of k otherwise. It is hoped that a pattern may emerge regarding divisibility properties.

The Sierpinski numbers are :

 k modulus factorisation covering set label 78557 36 17.4621 B 1.0 271129 24 prime A 2.0 271577 24 59.4603 A 3.0 322523 36 prime F 4.0 327739 48 prime C 5.0 482719 24 prime A 3.17 575041 24 29.79.251 A 2.6 603713 24 11.71.773 A 3.6 903983 24 149.6067 A 2.13 934909 36 prime D 6.0 965431 24 227.4253 A 2.18 1259779 36 23.54773 D 6.24 1290677 36 137.9421 E 7.0 1518781 24 11.138071 A 3.15 1624097 24 887.1831 A 2.11 1639459 24 prime A 2.16 1777613 72 29.61297 G 8.0 2131043 24 prime A 2.21 2131099 24 prime A 3.21 2191531 36 103.21277 B 1.31 2510177 36 167.15031 B 9.0 2541601 24 43.59107 A 3.11 2576089 36 prime B 9.21 2931767 24 859.3413 A 2.23 2931991 24 37.109.727 A 3.23 3083723 24 443.6961 A 2.5 3098059 24 prime A 3.5 3555593 24 23.154591 A 3.14 3608251 24 prime A 2.10 4067003 24 37.109919 A 3.10 4095859 36 41.283.353 E 7.29 4573999 24 prime A 3.13 5455789 48 59.89.1039 C 10.0 5841947 36 271.21557 E 11.0 6134663 24 19.322877 A 2.1 6135559 24 29.211571 A 3.1 6557843 24 37.177239 A 3.18 6676921 24 197.33893 A 2.2 6678713 24 prime A 3.2 6742487 24 1327.5081 A 2.7 6799831 24 prime A 3.7 6828631 36 23.337.881 D 12.0 7134623 36 232.13487 B 9.14 7158107 36 11.191.3407 E 7.20 7400371 24 11.101.6661 A 2.14 7523267 24 29.59.4397 A 2.19 7523281 24 prime A 3.19 7696009 36 83.92723 B 1.25 7761437 24 prime A 2.3 7765021 24 11.113.6247 A 3.3 7892569 24 31.47.5417 A 2.8 8007257 24 503.15919 A 3.8 8184977 36 prime B 13.0 8629967 24 41.210487 A 3.16 8840599 24 prime A 2.12 8871323 24 401.22123 A 2.17 8879993 48 prime C 10.33 8959163 36 prime E 14.0 9043831 48 283.31957 C 5.42 9044629 36 112.17.4397 E 7.13 9208337 24 prime A 2.15 9252323 36 prime E 11.14 9454129 24 37.255517 A 2.20 9454157 24 73.129509 A 3.20 9854491 24 163.60457 A 2.22 9854603 24 112.23.3541 A 3.22 9930469 24 prime A 2.4 9933857 36 312.10337 E 7.24 9937637 24 prime A 3.4

The counts for each covering set are as follows:

 Total A B C D E F G 69 45 7 4 3 8 1 1

In the above list, there are several obvious pairs, with differences, as follows :

271129 + 26.7 = 271577

2131043 + 23.7 = 2131099

2931767 + 25.7 = 2931991

6134663 + 27.7 = 6135559

6676921 + 28.7 = 6678713

7523267 + 2.7 = 7523281

7761437 + 29.7 = 7765021

9454129 + 22.7 = 9454157

9854491 + 24.7 = 9854603

where I have laid these out so that the striking similarity of the differences is apparent. Two other possible pairings, {8871323, 8879993} and {9043831, 9044629}, do not provide anything of interest, and the "closeness" of these pairs may be put down to co-incidence. There is one other grouping of interest, that is, the last three. The two consecutive differences do not indicate anything of significance. However, the following may seem rather striking :

9930469 + 210.7 = 9937637

In other words, the difference 2m.7 occurs once and only once for each m. It comes as no surprise to find that all these pairs have the same Sierpinski modulus and covering set, whereas the two other pairs mentioned do not. Additional investigation of differences between non-adjacent Sierpinski numbers reveals the following :

3083723 + 211.7 = 3098059

This effect is a direct result of the cyclic generating procedure, since if k and k' have the same covering set and we let x = k' - k, then the differences between successive iterations in the Keller cycle are just 2x, 4x, etc. In the above example, we may take the closest pairing, that is, k = 7523267 and k' = 7523281 as the starting values of the cycles.

Obviously, x = k' - k is even. The above example has x = 2*7. It would be interesting to find examples with x = 2*3 or 2*5, although at present no other pair of known Sierpinski numbers comes anywhere near as close as this.

We shall now continue the list to 2*107. It is obvious that the alternative iteration k ® (k+2P) provides an infinite sequence of Sierpinski numbers. However, these have identical properties to the associated base values and will be labelled with an asterisk. Applying the Keller iteration to any one of these generated values will re-create the Keller cycle for the base value. A Keller cycle is therefore uniquely defined by a base value N.0 and a covering set.

 10192733 24 prime A 2.9 10275229 36 31.461.719 B 9.5 10306187 36 prime E 15.0 10391933 36 prime B 1.10 10422109 24 47.221747 A 3.9 10675607 24 1297.8231 A 3.12 11000303 36 43.47.5443 E 15.22 11201161 36 23.487007 B 13.31 11206501 48 prime H 16.0 11455939 24 11.1041449 A * 11456387 24 prime A * 11667529 24 prime A * 11759851 24 661.17791 A * 11788523 24 prime A * 11822359 36 prime D 17.0 12088793 24 prime A * 12150241 24 521.23321 A * 12151397 36 149.81553 B or D or J 9.8 or 12.5 or 18.0 12384413 36 337.36749 B 9.26 12413281 36 17.191.3823 F 19.0 12703591 24 149.85259 A * 12756019 36 prime B 20.0 12808907 24 19.23.29311 A * 12824269 24 67.277.691 A * 13065289 36 89.146801 B 13.13 13085029 36 43.304303 B 1.13 13315853 24 43.309671 A * 13315909 24 prime A * 13726411 24 prime A * 14116577 24 prime A * 14116801 24 1873.7537 A * 14268533 24 23.41.15131 A * 14282869 24 397.35977 A * 14740403 24 prime A * 14793061 24 prime A * 15168739 36 3253.4663 B 19.20 15251813 24 19.67.11981 A * 15273751 48 prime I 21.0 15285707 36 prime D 12.13 15598231 36 112.17.7583 E 11.7 15758809 24 11.19.75401 A * 16010419 36 101.158519 E 15.5 16391273 36 71.230863 B 19.9 16625747 36 prime E 7.8 16907749 36 73.231613 E 11.25 16921847 36 prime F 18.13 17220887 36 3709.4643 D 22.0 17319473 24 prime A * 17320369 24 11.1574579 A * 17742653 24 prime A * 17861731 24 23.672.173 A * 17863523 24 601.29723 A * 17927297 24 prime A * 17984641 24 prime A * 18068693 36 prime E 11.30 18140153 36 prime B 9.34 18156631 36 prime B 9.19 18585181 24 prime A * 18708077 24 2707.6911 A * 18708091 24 prime A * 18946247 24 239.79273 A * 18949831 24 41.462191 A * 19077379 24 67.284737 A * 19192067 24 prime A * 19428919 36 prime E 15.13 19436611 36 197.98663 B 1.23 19558853 36 971.20143 B 13.34 19814777 24 19.47.22189 A *

where we have the additional coded covering sets :

 code modulus covering set H 48 {3, 5, 7, 17, 97, 241, 257} I 48 {3, 5, 7, 13, 17, 257, 673} J 36 {3, 5, 7, 13, 19, 73, 4033}

The algorithm actually located one value, k = 13965257, which had a zero intermediate weighting but a non-zero Nash weight and is therefore not a Sierpinski number.

As has been indicated above, it is entirely possible for a particular Sierpinski number to have more than one covering set. We shall call such numbers "overlapping" Sierpinski numbers, or "overlaps". The set J is not a true covering set since 4033 = 37*109 is not a prime. However, it is included in order to label these overlaps conveniently.

For covering set A, we have 2P(A) = 11184810. The only two base values with this covering set that are less than this bound are 271129 and 271577. Since the search has now passed this value of 2P, all other Sierpinski numbers with this covering set can be generated from one of these two by using either the Keller iteration or the additive iteration. This idea stretches to all Sierpinski numbers, that is, for a given covering set and modulus, all Sierpinski numbers k such that k > 2P have an associated base value k' such that k' < 2P. Thus there is a finite number of base values, and therefore also of Keller cycles, for each finite covering set.

None of the above Sierpinski numbers is divisible by 13. However, we cannot assume that this is a universal property. The reasoning for this is as follows: the number k = 11206501 has covering set H, as can be seen above, which does not contain 13. The product P(H) is approximately 1010 and the Sierpinski modulus is 48. Applying the Keller iteration and ignoring any number greater that 231 (which is the limit of the Nash-Jobling implementation of the Nash sieve), we are left with the following :

 iteration # Sierpinski number factorisation Sierpinski modulus 10 751375159 19.prime 48 14 1297920679 11.31.317.12007 24 38 701684269 11.13.19.101.2557 48 42 502866439 prime 48

Thus 701684269 is a Sierpinski number which is divisible by 13. A bonus here is that this value is 20 times smaller than the expected theoretical value.

Iteration 14 above is unusual. Although the original covering set still covers this value of k, the prime 13 has the same effect as 97 and 257 combined. We shall return to this idea shortly.

The 22 Keller cycles identified with smallest values less than 2*107 are divided amongst covering sets as follows :

 A 271129 (2) 271577 (3) B 78557 (1) 2510177 (9) 8184977 (13) 12756019 (20) C 327739 (5) 5455789 (10) D 934909 (6) 6828631 (12) 11822359 (17) 17220887 (22) E 1290677 (7) 5841947 (11) 8959163 (14) 10306187 (15) F 322523 (4) 12413281 (19) G 1777613 (8) H 11206501 (16) I 15273751 (21) J 12151397 (18)

where the values in brackets are the labels given to the Sierpinski number in the earlier lists.

There are 7 Sierpinski numbers that overlap between cycles with different covering sets. These are :

12151397 - shared by cycles 9 (B) and 12 (D)

45181667 - shared by cycles 13 (B) and 6 (D)

68468753 - shared by cycles 1 (B) and 17 (D)

69169397 - shared by cycles 21 (D) and 11 (E)

71307347 - shared by cycles 1 (B) and 17 (D)

182479909 - shared by cycles 12 (D) and 14 (E)

392581699 - shared by cycles 6 (D) and 18 (F)

The four overlaps involving covering sets B and D are similar in that the primes 37 and 109 are directly interchangeable since they cover the same exponents, that is, have the same Nash congruence. Since these two primes both have exponent 36 to base 2, there is a 35 to 1 chance that a Sierpinski number covered by B or D is covered by both B and D. Any overlap between B and D is automatically covered also by J since 4033 = 37*109.

The two overlaps involving covering sets D and E are more complicated in that the subsets {3,5,73) of D and {3,5,37} of E are interchangeable but no smaller subsets are interchangeable. This is because the Nash congruence for 37 is 27 mod 36 and for 73 is 0 mod 9. Thus 73 covers everything covered by 37 but the reverse is not the case. However, 0, 9 and 18 mod 36 are covered by the primes 3 and 5 so the net effect of the triplets is the same. Similarly, with the overlap involving covering sets D and F, the subsets {5,19} and {5,37} are interchangeable since 19 covers both 4 and 22 mod 36 whereas 37 covers only 22 mod 36, but the prime 5 covers all numbers divisible by 4. In the event of an overlap between D and E or D and F, the set D is considered to be the better covering set since the exponent of the exceptional prime is lower in each case.

Other overlaps exist, for instance the one mentioned previously with respect to the search for a Sierpinski number divisible by 13, in which the overlap involves covering sets of different moduli. A complete picture of overlaps involving covering set A is missing since the product of primes is so small that it requires generated values to match those in Keller cycles of other covering sets and only base values where compared above.

Continuing the search to 5*107 reveals 3 more covering sets, 7 more Keller cycles and 8 more overlaps between different Keller cycles. Ignoring those Sierpinski numbers with modulus 24 (as they are all generated values), the list continues :

 20189993 36 967.20879 E 11.10 20312899 36 43.472393 B 13.29 20778931 36 71.292661 B 13.11 21610427 36 prime B 20.7 21823667 48 937.23291 C 5.19 22024609 72 1303.16093 K 23.0 22047647 36 1481.14887 B 9.32 23277113 36 79.294647 D 6.13 23487497 36 11.2135227 E 15.8 24885199 48 113.191.1153 L 24.0 25614893 36 23.311.3581 E 14.24 25763447 48 983.26209 C 10.15 25912463 36 47.479.1151 D 6.33 26471633 36 672.5897 E 7.34 27160741 36 373.72817 B 9.11 27862127 36 29.960763 F 25.0 28410121 36 113.251417 E 7.11 29024869 36 67.433207 B 9.29 29095681 36 839.34679 F 25.27 29949559 48 prime C 5.32 30375901 36 prime E 11.23 30423259 36 prime B 20.28 30666137 36 29.47.149.151 E 11.28 31997717 36 prime B 20.3 32548519 36 23.53.26701 B 20.24 32552687 36 67.289.1249 E 14.22 32971909 36 311.106019 D 6.8 33234767 36 prime B 20.31 33485483 36 prime B 13.6 33742939 36 283.119233 E 11.21 34167691 36 929.36779 B 20.14 34471877 36 11.1493.2099 B 13.16 34629797 36 193.179429 B 1.16 34636643 36 23.29.51929 B 13.22 34689511 36 prime D 12.28 35430841 36 127.227.1229 F 4.21 36029731 72 71.507461 G 26.0 36120983 36 31.1165193 B 1.30 36234799 36 3307.10957 E 14.31 37158601 48 prime M 27.0 38206517 36 prime D 12.17 38222131 36 349.109519 E 15.27 38257411 36 prime D 22.19 38592529 36 4937.7817 B 9.13 38750753 36 2971.13043 E 14.4 38942027 36 1049.37123 E 14.14 39953689 36 17.2350217 E 11.33 40118209 36 prime E 7.17 40343341 36 prime E 14.33 40511719 36 43.83.11351 E 15.33 41134369 48 prime L 28.0 41403227 36 3533.11719 B 20.35 42609587 36 prime B 20.19 43441313 36 211.205883 E 11.18 43925747 36 43.107.9547 F 25.4 44091199 36 prime E 14.11 44103533 36 4751.9283 B 9.18 44743523 36 11.4067593 B 1.22 45181667 36 prime B or D or J 13.28 or 6.19 or 29.0 45414683 36 61.744503 B 13.10 45830431 36 31.491.3011 B 20.6 46049041 36 prime B 9.31 46337843 36 4327.10709 D 22.14 47635073 36 prime F 19.23 48292669 36 151.319819 E 15.29 48339497 36 107.451771 D 17.15

The new covering sets are :

 code modulus covering set K 72 {3, 5, 7, 13, 17, 19, 37, 433} L 48 {3, 5, 7, 13, 17, 97, 673} M 48 {3, 5, 13, 17, 97, 241, 257}

The last of these does not have the prime 7 as a member. Although the value k = 37158601 is a prime, the Keller cycle associated with it contains seven members that are divisible by 7, the lowest of which is k = 1905955429. In fact, another member of the cycle, k = 16352358743, is divisible by 72. The direct search algorithm used to locate the Sierpinski numbers listed above ignores numbers divisible by 7, but the nature of the Keller iteration ensures that most of members of the Keller cycle are not, and so once one of these is found, any smaller member of the cycle can be retrieved. An example of this will eventually be forthcoming.

The additional overlaps found are :

154337567 - shared by cycles 17 (D) and 25 (F)

226521259 - shared by cycles 6 (D) and 29 (J)

236281883 - shared by cycles 6 (D) and 29 (J)

282777829 - shared by cycles 12 (D) and 18 (J)

300943667 - shared by cycles 17 (D) and 25 (F)

343302301 - shared by cycles 17 (D) and 25 (F)

1300668683 - shared by cycles 8 (G) and 23 (K)

4213021013 - shared by cycles 8 (G) and 23 (K)

The overlaps shared by sets D and J also occur as generated values for set B. The overlaps involving G and K are also based around the 37-109 interchangeability.

Totals for Sierpinski numbers by covering set are :

 Total A B C D E F G H I J K L M 332 213 44 7 14 36 8 2 1 1 2 1 2 1

where the two overlaps that fall into the search range have been assigned to covering set J.

We now complete the search to 108. As before, we shall ignore the generated values associated with covering set A.

 50236847 36 5779.8693 B 20.27 50273851 36 prime F 4.33 50407157 36 73.690509 E 14.6 50835497 36 23.139.15901 E 15.16 51172253 36 11.97.199.241 E 14.16 51299477 36 prime B 20.23 51612259 72 149.346391 N 30.0 51642601 36 prime B 20.30 51767959 36 3109.16651 B 13.5 51889823 72 2347.22109 P 31.0 52109063 36 17.257.11927 B 20.13 52343539 36 131.463.863 B 13.21 53085709 36 79.671971 B 1.29 54345857 36 prime E 7.28 55218901 36 71.777731 E 11.35 55726831 36 412.33151 B 20.34 55876981 36 1373.40697 E 7.19 56191673 72 79.711287 P 31.48 56330011 36 173.325607 B 20.18 56517767 36 7013.8059 F 4.30 56777509 36 127.447067 E 14.35 56924089 36 113.503753 E 11.13 57396979 36 2557.22447 B 1.21 57410477 36 127.251.1801 D 6.11 57451021 36 389.147689 E 15.35 57616051 36 1021.56431 B 13.27 57732559 36 83.695573 B 13.9 57798079 36 17.3399887 E 15.21 57816799 36 53.1090883 F 32.0 57940433 36 821.70573 B 20.5 59198569 72 prime K 33.0 59929127 36 479.125113 F 4.14 60097043 36 5653.10631 E 11.6 60143641 36 prime B 20.26 60303137 36 prime E 15.4 60610801 36 prime E 7.7 60666107 36 19.3192953 F 32.3 60909197 36 89.684373 B 13.4 61079749 36 167.365747 B 20.12 61196987 36 prime B 13.20 62012387 36 131.473377 E 15.12 62888633 36 prime B 20.33 63190223 36 23.2747401 B 20.17 63662611 36 5381.11831 F 25.31 63676073 36 prime D 17.13 63723707 36 71.897517 B 1.20 63833243 36 4951.12893 B 13.26 63891497 36 887.72031 B 13.8 65623711 36 prime B 13.19 66620329 36 2267.29387 B 20.16 66887071 36 929.71999 B or F 1.19 or 32.14 66941839 36 prime B 13.25 67510217 36 103.655439 D 17.11 67800683 48 19.3568457 L 24.25 67837073 36 2749.24677 B 13.18 68468753 36 179.382507 B or D or J 1.18 or 17.9 or 34.0 68496137 36 prime B 13.24 68574271 36 prime E 14.21 68708387 36 11.61.102397 D 17.7 69169397 36 11.227.27701 E or D 11.20 or 22.4 69265069 36 67.1033807 F 19.30 70207549 36 2557.27457 B 1.1 70312793 36 601.116993 D 22.6 70364663 36 prime B 1.2 70415327 36 41.1717447 E 14.30 70678891 36 101.699791 B 1.3 71151293 36 31.163.14081 D 12.31 71307347 36 31.313.7349 B or D or J 1.4 or 17.31 or 34.22 71408993 36 17.4200529 E 15.26 71476051 36 137.521723 D 22.31 71768941 36 151.461.1031 E 14.13 72553787 36 587.123601 E 15.32 72564259 36 1223.59333 B 1.5 74343527 36 5591.13297 E 14.10 74433497 36 17.23.190367 B 1.32 74886377 36 17.41.107441 D 22.8 75037639 48 31.2420569 C 5.16 75070789 36 557.134777 B 9.1 75078083 36 2699.27817 B 1.6 75202613 36 prime B 9.22 77564731 36 71.1092461 F 4.17 77807131 48 prime L 24.6 78240377 36 prime D 12.33 78816559 36 prime B 1.33 78864593 36 643.122651 D 17.33 79539409 36 523.152083 D 22.33 80091143 36 11.59.123407 B 9.2 80105731 36 5737.13963 B 1.7 80354791 36 11.7304981 B 9.23 81196967 36 31.2619257 E 15.20 81722987 36 179.456553 D 12.25 82346449 36 89.925241 E 11.5 83304121 36 1063.78367 E 15.11 83460571 36 71.367.3203 F 32.6 84319681 36 173.487397 B 9.15 85442453 36 241.354533 B 1.26 86420389 36 11.7856399 B 13.1 86585063 36 17.317.16067 E 14.20 87376127 36 127.397.1733 F 32.23 87505591 36 31.2822761 E 14.29 87582683 36 41.2136163 B 1.34 88574821 36 prime E 15.31 89469691 36 17.5262923 E 14.9 90131851 36 113.797627 B 9.3 90161027 36 11.59.138923 B 1.8 90600893 36 prime B 9.6 90659147 36 17.317.16823 B 9.24 90834301 36 2437.37273 B 1.11 92452757 36 31.173.17239 B 13.32 92732027 48 19.37.131909 C 5.11 92896411 36 347.267713 E 15.19 93180713 36 4793.19441 D 22.10 94353229 36 prime B 9.9 94741307 36 5471.17317 D 17.27 94751851 36 1109.85439 D 22.27 94819261 36 1153.82237 B 9.27 95562473 36 103.927791 B 20.1 95590459 36 1163.82193 E 14.19 96050723 36 7487.12829 E 14.28 96181013 36 1151.83563 B 13.14 96220493 36 17.53.269.397 B 1.14 97032773 36 41.2366653 E 14.8 98588927 36 499.197573 B 9.16 98746133 36 2011.49103 E 15.18 98915393 48 37.1097.2437 L 24.21 99287341 36 6451.15391 D 12.20 99694493 36 41.2431573 D 22.22

The new covering sets are :

 code modulus covering set N 72 {3, 5, 7, 17, 19, 37, 109, 241} P 72 {3, 5, 7, 17, 19, 37, 73, 241}

Additional overlaps found including new cycles are :

66887071 - shared by cycles 1 (B) and 32 (F)

114921271 - shared by cycles 7 (E) and 32 (F)

122311103 - shared by cycles 22 (D) and 32 (F)

133228283 - shared by cycles 7 (E) and 32 (F)

192413177 - shared by cycles 22 (D) and 32 (F)

In the B & F overlap, the subsets {5,19} and {5,109} are interchangeable. The overlaps involving sets E and F are as a result of a {3,19} and {3,73} interchange. Since 73 has the smaller exponent, the primary covering set is F.

From the data obtained, it is increasingly obvious that for each different covering set there will be an even number of distinct Keller cycles. This conjecture is definitely true of set A, since the 2P barrier has been reached. Continuing the search to 1.5*108 would pass the 2P barrier for set B. At the moment, there are 4 Keller cycles associated with set B, and it is unlikely that any more will be found. There are also 4 distinct Keller cycles currently known for sets D, E and F, with no more expected. Justification for the conjecture is as follows.

Suppose k is a Sierpinski number with covering set P = {p1, p2, …} and modulus m and such that k < 2P. Let ei be the exponent of pi to base 2, (so that lcm(e1, e2, …) = m) and let the Nash congruences associated with P be (pi, ri). The j-th step of the Keller iteration k ® (2k+P) mod 2P changes the Nash congruences to (pi, ri - j), in effect, sliding the divisibility properties one place to the left. Since the ri are all reduced modulo ei , the m-th step re-aligns all the congruences and we arrive back at k. Thus we have the Keller cycle relating m different Sierpinski numbers. However, rather than simply shifting the congruences by 1, we may consider flipping the congruences about the midpoint m/2. In this case, the new congruences are (pi, m+1- ri) associated with a mirror-image or flip Sierpinski number k'. The second term here can be replaced by ei+1- ri since ei divides m. Repeating this flip returns the original values. We have k.+1 º 0 mod pi and so k º - mod pi . Replacing the exponent, we have k' º - mod pi . We then have a set of simultaneous congruences that can be solved to obtain k' < 2P, k odd, which always exists by the Chinese Remainder Theorem. We can then generate a flip cycle using the Keller iteration.

As an example, k = 271129 has covering set A, modulus 24, and Nash congruences obtained using psieve are (3,1) (5,0) (7,2) (13,6) (17,6) and (241,10) and Keller label 2.0. Since the primes involved have exponents 2, 4, 3, 12, 8 and 24 respectively, the flipped Nash congruences are (3,0) (5,1) (7,2) (13,7) (17,3) and (241,15), leading to the set of congruences k' º 2 mod 3, k' º 2 mod 5, k' º 5 mod 7, k' º 7 mod 13, k' º 2 mod 17, k' º 211 mod 241. The smallest solution of this is k' = 271577, which is the smallest value in the only other Keller cycle for set A (Keller label 3.0). Thus there is a direct match between members of the two Keller cycles, that is, the j-th Keller iterations are flips of each other for all j < 24.

A more complicated example is provided by k = 78557 (Keller label 1.0), the smallest Sierpinski number. This has covering set B, modulus 36, and Nash congruences (3,0) (7,1) (5,1) (73,3) (13,11) (19,15) and (37,27), giving flip congruences (3,1) (7,0) (5,0) (73,7) (13,2) (19,4) and (37,10). Evaluating the flip Sierpinski number, we find k' = 29024869, which has Keller label 9.29. In other words, the flip does not directly match up the Keller labels and requires 29 Keller iterations to do so. We shall call the number of Keller iterations between the base values of the two Keller cycles the flip offset. The flip of 9.0 is, unsurprisingly, found to be 1.29. Rather than slide left 29 places, we could slide right 7 places, by replacing Nash congruences (pi, ri) with (pi, rI+7). However, there is no simple iteration that performs a slide to the right.

In the above example, the number of Keller iterations required is odd, and so there is no label position at which flips match. However, for k = 8184977, labelled 13.0, and which also has covering set B, the flip k' = 66620329 has Keller label 20.16. Since the offset is even, there is a position at which matching labels are flips of each other. This happens at the 8th iteration, that is, Sierpinski numbers 13.8 and 20.8 are flips of each other.

The only problem with our conjecture is the possibility that the flipping process might map every congruence onto itself, and hence k º k' (to within Keller cycles). Suppose the flip is self-mapping, and let p be a member of the covering set such that p has largest exponent ep. The Nash congruence (p,r) flips to (p,r+x) for some offset of x. Therefore, we require m+1- r º r- x mod ep, that is, 2r º 1- x mod ep. Since there must be other Nash congruences covering all positions from 1 to m, there must be another prime, q say, such that q covers position r+1. By symmetry, the congruence (q,r+1) flips to (q,r+x- 1). Hence m+1- (r+1) º r+x- 1 mod eq, that is 2r º 1- x mod eq . In general, each prime pi ¹ p in the covering set covers position r+yi for some value yi, and we find that 2r º 1- x mod ei for all i. Now, using the Keller iteration, we can suppose that r = m, since otherwise we can find another member of the Keller cycle for which this is the case. Thus we have x º 1 mod ei for all i. Now, if ei is even, x must be odd, and vice-versa, and hence the ei are either all odd or all even. Also, if there is a prime whose exponent is m, we must have x = 1 since by definition we have x < m.

Suppose the ei are all odd. Then the primes 3 and 5 are immediately ruled out of the covering set. In fact, there are comparatively few primes with odd exponent. The first few are 7, 23, 31, 47, 71, 73, 79, 89, 103, 127, 151, 167, 191, 199, 223, 233, 239. The smallest covering sets that do not include 5 are of modulus 72, there being 7 of these, and they all include 3. The smallest covering set that does not include 3 has modulus 180 and has 16 primes, whose product is approximately 2*1030. All covering sets of modulus 180 include either 3 or 5. There are modulus 360 covering sets that contain neither 3 nor 5, but most of the other primes in these sets have even exponent. A covering set made up entirely of primes with odd exponent would have a huge modulus.

Suppose the ei are all even. Then they must all be powers of 2 since otherwise we could replace primes of order ei with primes of odd exponent fi such that fi divides ei. Consider modulus m = 64. There is only one covering set, consisting of all the primes dividing 264 - 1, and one self-flipping Keller cycle, whose smallest value is offset by 29 when flipped.

Proceeding with the flip idea, we can pair up all the known Keller cycles, and also find new ones that lie outwith the current search range. For instance, set H (modulus 48) is associated with only one Keller cycle for k < 108, starting at k = 11206501. The Nash congruences are (3,1) (7,2) (5,2) (17,0) (257,4) (241,12) and (97,28). The flip congruences are (3,0) (7,2) (5,3) (17,1) (257,13) (241,13) and (97,21). Solving the generated simultaneous congruences gives k' = 8407945943. The Keller cycle produced from this has smallest value k'' = 597875869, which is therefore labelled as the zeroth member of the cycle, and k' is 5 Keller iterations from this. Thus we have found a matching Keller cycle for the one we already knew, with an offset of 5.

For completeness, of the 34 Keller cycles found during the search over k < 108, we have the following flipping pairs, using label numbers and giving a flip offset.

 A 2 & 3 offset 0 B 1 & 9 offset 29 13 & 20 offset 16 C 5 & 10 offset 27 D 6 & 22 offset 20 12 & 17 offset 17 E 7 & 14 offset 19 11 & 15 offset 33 F 4 & 25 offset 19 19 & 32 offset 13 L 24 & 28 offset 7

The two Keller cycles 8 and 26 associated with set G do not constitute a pair, but are both paired with cycles outwith the current search range. The same is true of the two cycles associated with set K, though the standard calculations lead to a base value k = 115281169, not much beyond the current limits, whose Keller cycle pairs with cycle 23.

Note that using the alternative congruences (pi, m- ri) as the flip congruences instead of

(pi, m+1- ri) does not change the pairing of Keller cycles, but increases the offset by 1 (modulo m).

We now continue the search to 2*108. For covering set B, 2P(B) is reached within this range, and no generated values are listed.

 100093157 36 prime E 14.18 100323289 36 11. E 14.27 100387913 36 prime B 20.21 100834471 36 prime B 1.27 102310339 36 D 17.20 102790343 36 prime B 13.2 102832981 36 B 20.10 103812287 36 41. D 6.23 104697533 36 61. F 19.11 105114931 36 59. B 1.35 105885947 72 R 35.0 106330741 36 11. B 9.35 106363697 36 11.31. B 9.20 106596713 36 101. D 12.35 107177209 36 prime E 7.1 107432603 36 113.167. F 25.34 108628343 72 151. S 36.0 108923657 36 prime B 1.24 109093577 36 23. D 17.35 109168141 36 107.197. B 13.35 109758563 36 E 7.2 110213267 36 127. B 9.4 110271619 36 31.139.157.163 B 1.9 110676233 36 prime B 13.30 110825251 36 prime D 12.12 111151351 36 prime B 9.7 111267859 36 23. B 9.25 111608297 36 97. B 13.12 111618167 36 prime B 1.12 111792841 36 prime D 22.35 112787573 36 prime E 7.30 113271289 36 17.223. B 20.8 114145729 36 53. B 9.33 114596513 36 337. F 4.28 114855079 36 101. B 13.33 114921271 36 E or F 7.3 or 32.34 115281169 72 K 37.0 115449353 36 F 4.12 115566797 72 R 35.44 116138629 36 D 6.32 116279749 36 E 11.1 117188839 36 F 32.12 118656023 36 B 9.10 118912069 36 E 7.21 119588087 36 B 9.28 119863547 48 C 10.7 119879899 48 C 5.24 120527153 36 D 12.27 120979291 36 E 7.31 121074511 36 B 20.2 122091961 48 C 10.26 122311103 36 D or F 22.18 or 32.21 122311591 36 B 13.15 122390551 36 B 1.15 122514181 36 E 14.1 122685113 36 E 7.14 123100501 36 E 11.15 124371917 36 B 9.12 124463569 36 E 7.25 125208229 36 E 15.1 125246687 36 E 7.4 125773231 36 D 6.18 126351319 36 D 22.13 126596461 36 E 15.23 127127419 36 B 9.17 127963643 36 E 11.2 128100173 36 B 9.30 129197389 36 F 32.32 129764281 36 F 32.10 130725391 36 B 20.22 130896953 36 B 20.29 131044847 36 F 32.19 131618507 36 B 1.28 133228283 36 E or F 7.22 or 32.17 134045869 36 B 20.4 135147473 36 B 20.25 135229937 36 F 25.20 135530251 36 B 13.3 135615527 36 B 20.11 135792317 36 E 11.8 136519969 36 B 20.32 136616693 36 E 15.6 137021401 36 B 13.7 137362727 36 E 7.32 137536591 36 D 17.6 137847349 36 E 7.9 138385817 36 B 20.15 138411353 36 E 11.26 138836071 36 D 17.30 138920423 36 D 22.30 138994189 36 B 13.17 139051463 36 F 25.22 139310029 36 B 1.17 139323721 36 B 13.23 139630819 36 F 19.18 140432507 36 E 14.2 140733241 36 E 11.31 140774371 36 E 7.15 141605147 36 E 11.16 143453693 36 E 15.14 144043891 36 D 12.24 144331283 36 E 7.26 144975841 36 E 11.11 145820603 36 E 15.2 145897519 36 E 7.5 146053577 72 G 38.0 146880319 48 C 5.40 148597067 36 E 15.24 150553051 36 D 17.26 150558323 36 D 22.26 151060223 48 C 10.13 151331431 36 E 11.3 151570849 36 E 15.9 152106751 48 C 5.30 152252267 36 F 19.33 154337567 36 D or F 17.19 or 25.24 155088541 36 D 6.22 155223473 72 S 39.0 155825641 36 E 14.25 156654991 36 F 19.20 156701453 72 P 40.0 157539121 36 E 7.35 158595023 36 D 12.11 161416097 36 E 7.12 161860711 36 E 7.23 163378771 48 C 5.14 164337949 36 D 22.17 165025171 36 F 4.25 165347657 36 E 11.24 165928129 36 E 11.29 166069013 36 D 6.17 166358057 36 D 22.12 166988779 36 E 11.9 167604349 36 F 25.17 168637531 36 E 15.7 169073869 60 T 41.0 169701229 36 E 14.23 170129599 36 E 7.33 170337737 72 K 37.27 171098843 36 E 7.10 171950693 36 D 17.5 172081733 36 E 11.22 172226851 36 E 11.27 172600433 36 D 17.29 172642609 36 D 22.29 174329011 60 U 42.0 175204343 36 D 12.23 176269159 36 E 14.3 176870627 36 E 11.32 176952887 36 E 7.16 177065453 36 E 14.32 178458923 36 D 17.25 178461559 36 D 22.25 178614439 36 E 11.17 180351181 36 D 17.18 181040117 36 E 15.28 181339441 48 C 5.38 182097361 36 E 14.5 182311531 36 E 15.15 182384417 48 C 10.11 182479909 36 D or E 12.10 or 14.15 182646049 48 C 5.28 184066711 36 E 7.27 184503233 36 E 11.34 184832273 36 E 7.18 185282537 36 E 14.34 185355827 36 E 11.12 185619293 36 E 15.34 187045351 36 E 15.3 187199183 36 E 7.6 190784569 36 D 12.22 191478481 36 E 11.19 192411859 36 D 17.24 192413177 36 D or F 22.24 or 32.27 192598279 36 E 15.25 192778253 36 E 14.12 198067007 36 E 11.4 198545843 36 E 15.10 199388327 36 D 17.23

This range provides us with the first Sierpinski numbers of modulus 60. Covering sets and sample Sierpinski numbers with modulus 60 have been obtained using alternative methods previously, but the smallest such numbers had not.

The new covering sets are :

 code modulus covering set R 72 {3, 5, 7, 13, 17, 37, 109, 433} S 72 {3, 5, 7, 13, 17, 19, 73, 433} T 60 {3, 5, 7, 11, 13, 41, 61, 151, 331} U 60 {3, 5, 7, 11, 13, 31, 41, 61, 331}

Additional overlaps found including new cycles are :

8664092933 - shared by cycles 23 (K) and 39 (S)

9863014727 - shared by cycles 36 (S) and 37 (K)

9936760217 - shared by cycles 36 (S) and 37 (K)

11968332053 - shared by cycles 8 (G) and 35 (R)

21530959441 - shared by cycles 8 (G) and 35 (R)

24733157753 - shared by cycles 8 (G) and 35 (R)

The overlaps involving sets K and S result from interchangeability of the subsets {3,5,37} and (3,5,73}. Since 73 has smaller exponent than 37, set S is the primary covering set. The G & R overlap is caused by interchanging the sets {5,19} and {5,37}.

If we continue, the limit 2P(E) = 209191710 is reached quickly and no new cycles with covering set E are found. The following list takes us as far as 2P(D) = 412729590.

 200019049 36 F 25.9 201181193 36 E 15.30 202876561 36 D 17.22 205410169 36 E 14.7 206266849 36 E 15.17 206940361 36 E 14.17 207055427 36 E 14.26 207140783 36 F 19.35 208234613 36 D 6.1 208884353 36 D 6.25 210104431 36 D 6.2 210465533 72 P 43.0 210586403 72 P 40.36 211062227 72 V 44.0 211073063 72 K 23.21 211403911 36 D 6.26 212497043 72 W 45.0 213447751 48 I 21.28 213578567 48 I 46.0 213844067 36 D 6.3 214767383 72 P 43.48 215481983 36 F 25.26 216443027 36 D 6.27 218039041 48 C 10.30 218649563 36 F 4.20 220022057 36 D 12.1 221323339 36 D 6.4 224129461 72 G 26.24 224751679 36 F 19.22 225632671 48 L 24.14 226521259 36 D or J 6.28 or 29.9 228505373 48 L 28.17 230009513 36 D 17.1 230667589 36 D 12.6 232190537 48 C 10.23 233679319 36 D 12.2 235566677 36 F 19.29 236281883 36 D or J 6.5 or 29.22 236936209 36 D 12.14 240806569 36 D 22.1 240936503 72 K 47.0 245952859 48 C 10.20 246677723 36 D 6.29 252919021 36 D 6.14 253282909 36 F 19.10 253424869 48 C 10.44 253654231 36 D 17.2 254970383 36 D 12.7 258189721 36 D 6.34 258232399 36 F 4.27 258658819 36 F 4.11 260993843 36 D 12.3 265532837 36 F 32.31 265816283 36 F 32.9 266142407 60 X 48.0 266198971 36 D 6.6 267507623 36 D 12.15 268549111 36 F 25.19 272308613 36 D 6.9 275248343 36 D 22.2 275743817 36 D 12.29 278770729 48 Y 49.0 282777829 36 D or J 12.18 or 18.13 282879617 36 D 22.20 284736317 36 F 25.16 286604449 48 L 28.44 286990651 36 D 6.30 290215763 48 L 24.17 291966617 48 C 10.47 292099127 60 X 50.0 293678719 48 C 10.32 296728129 36 D 6.20 297140731 36 F 32.26 297988073 60 X 51.0 299040481 36 D 22.15 299473247 36 D 6.15 300943667 36 D or F 17.3 or 25.8 301946329 48 L 28.40 303043789 36 D 17.16 303126409 72 S 36.51 303575971 36 D 12.8 308587501 72 N 30.34 308914459 72 Z 52.0 310014647 36 D 6.35 313197379 48 L 28.20 314416021 72 K 37.6 315622891 36 D 12.4 318717481 36 F 19.28 321185749 36 D 6.12 326033147 36 D 6.7 327575597 36 F 19.9 328650451 36 D 12.16 332320309 60 X 53.0 333700561 36 F 32.30 333716941 36 D 17.14 338252431 36 D 6.10 338513269 48 L 28.12 341371831 48 AA 54.0 341385229 36 D 17.12 343302301 36 D or F 17.10 or 25.15 343401623 48 L 24.41 343781569 36 D 17.8 344131891 36 D 22.3 344703589 36 D 22.5 345122839 36 D 12.30 346990381 36 D 22.7 348667381 36 D 12.32 348979489 36 D 17.32 349316897 36 D 22.32 350284703 48 C 10.25 351639391 48 L 28.26 354064201 72 Z 52.38 356137549 36 D 22.9 359190863 36 D 12.19 359292259 48 AB 55.0 359394439 36 D 22.21 360292883 36 F 19.27 361019063 72 G 8.56 362845549 36 D 12.34 364093981 36 D 17.34 364721941 36 F 19.8 365443613 36 D 22.34 365928503 72 AC 56.0 367616507 36 D 6.31 367784423 36 F 32.29 369699767 72 R 57.0 369810769 36 D 12.26 372585293 36 F 25.14 379908443 48 C 5.37 380430931 48 C 10.10 380561747 48 C 5.27 383295113 36 F 19.7 384932701 48 L 24.46 387091463 36 D 6.21 387226789 36 F 25.13 388176109 72 P 31.39 391716167 36 D 22.16 392581699 36 D or F 6.16 or 19.6 392726221 36 D 22.11 394547537 36 F 25.12 395522539 36 D 17.4 395847409 36 D 17.28 395868497 36 D 22.28 398207911 36 F 25.11 398258243 48 C 10.29 399722783 36 D 17.17 400787147 36 D 12.9 402513331 36 F 4.1 403158377 36 F 4.2 404448469 36 F 4.3 404939477 36 D 12.21 405333991 48 C 10.22 405753781 36 D 22.23 407028653 36 F 4.4 408182963 72 G 26.43 410985473 36 D 17.21 412189021 36 F 4.5

The new covering sets are :

 code modulus covering set V 72 {3, 5, 7, 17, 37, 109, 241, 433} W 72 {3, 5, 7, 13, 19, 109, 241, 433} X 60 {3, 5, 7, 11, 13, 31, 41, 61, 151} Y 48 {3, 5, 7, 13, 97, 241, 673} Z 72 {3, 5, 13, 17, 19, 37, 109, 241} AA 48 {3, 5, 7, 17, 97, 257, 673} AB 48 {3, 5, 13, 17, 97, 241, 673} AC 72 {3, 5, 7, 13, 19, 37, 241, 433}

Note that we have run out of convenient letters to identify covering sets, and it is appropriate to develop a new nomenclature.

Two of the new covering sets do not include the prime 7. In fact, the value of 52.0 was initially overlooked by the algorithm since it divisible by 7, and only located by generating the Keller cycle from 52.38. It is possible that other Sierpinski numbers have been similarly overlooked, but, as mentioned previously, will eventually be discovered. However, it is likely that 52.0 is the smallest Sierpinski number divisible by 7.

Another interesting development is the occurrence of 4 closely grouped values all with covering set X but all in different cycles.

An additional overlap occurs between cycles with covering sets K & R. Many mnore overlaps between members of Keller cycles and generated values exist.

The current allocation of covering sets to Keller cycles, ignoring set J, is as follows:

 set modulus cycles status A 24 2, 3 (complete) B 36 1, 9, 13, 20 (complete) C 48 5, 10 D 36 6, 12, 17, 22 (complete) E 36 7, 11, 14, 15 (complete) F 36 4, 19, 25, 32 G 72 8, 26, 38 H 48 16 I 48 21, 46 K 72 23, 33, 37, 47 L 48 24, 28 M 48 27 N 72 30 P 72 31, 40, 43 R 72 35, 57 S 72 36, 39 T 60 41 U 60 42 V 72 44 W 72 45 X 60 48, 50, 51, 53 Y 48 49 Z 72 52 AA 48 54 AB 48 55 AC 72 56

We now continue to 5*108.

 415951157 48 C 10.43 422509757 36 F 4.6 422590909 72 P 31.15 425780911 48 I 46.35 426694847 36 F 19.1 435119569 48 L 24.12 435222031 48 C 10.46 435711979 36 F 19.14 443151229 36 F 4.7 450231953 72 G 26.51 451521409 36 F 19.2 456324301 48 I 46.27 457592539 36 F 25.1 460059647 36 F 25.28 464561807 48 L 24.39 466621249 48 L 28.24 469555673 36 F 19.15 472729967 36 F 4.22 478078081 48 AA 58 482420221 72 G 59 484434173 36 F 4.8 488303521 60 X 60 489719779 36 F 25.5 494851853 48 L 24.37 497138431 36 F 19.24 497214301 48 C 10.42 497369479 60 X 61

There are 3340 distinct Sierpinski numbers identified to this point, of which 657 belong to at least one Keller cycle. This includes only one, namely 308914459, that is divisible by 7.

Complete listing of Sierpinski numbers