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

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 < 10⁷. As a comparison, the algorithm was run for all k < 5.10⁶ 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 2^s - 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 :

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 :

The counts for each covering set are as follows:

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

271129 + 2⁶.7 = 271577

2131043 + 2³.7 = 2131099

2931767 + 2⁵.7 = 2931991

6134663 + 2⁷.7 = 6135559

6676921 + 2⁸.7 = 6678713

7523267 + 2.7 = 7523281

7761437 + 2⁹.7 = 7765021

9454129 + 2².7 = 9454157

9854491 + 2⁴.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 + 2¹⁰.7 = 9937637

In other words, the difference 2^m.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 + 2¹¹.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*10⁷. 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.

where we have the additional coded covering sets :

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 10¹⁰ and the Sierpinski modulus is 48. Applying the Keller iteration and ignoring any number greater that 2³¹ (which is the limit of the Nash-Jobling implementation of the Nash sieve), we are left with the following :

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*10⁷ are divided amongst covering sets as follows :

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*10⁷ 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 :

The new covering sets are :

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

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

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

The new covering sets are :

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*10⁸ 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 = {p₁, p₂, …} and modulus m and such that k < 2P. Let e_i be the exponent of p_i to base 2, (so that lcm(e₁, e₂, …) = m) and let the Nash congruences associated with P be (p_i, r_i). The j-th step of the Keller iteration k ® (2k+P) mod 2P changes the Nash congruences to (p_i, r_i - j), in effect, sliding the divisibility properties one place to the left. Since the r_i are all reduced modulo e_i , 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 (p_i, m+1- r_i) associated with a mirror-image or flip Sierpinski number k'. The second term here can be replaced by e_i+1- r_i since e_i divides m. Repeating this flip returns the original values. We have k.+1 º 0 mod p_i and so k º - mod p_i . Replacing the exponent, we have k' º - mod p_i . 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 (p_i, r_i) with (p_i, r_I+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 8^th 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 e_p. The Nash congruence (p,r) flips to (p,r+x) for some offset of x. Therefore, we require m+1- r º r- x mod e_p, that is, 2r º 1- x mod e_p. 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 e_q, that is 2r º 1- x mod e_q . In general, each prime p_i ¹ p in the covering set covers position r+y_i for some value y_i, and we find that 2r º 1- x mod e_i 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 e_i for all i. Now, if e_i is even, x must be odd, and vice-versa, and hence the e_i 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 e_i 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*10³⁰. 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 e_i are all even. Then they must all be powers of 2 since otherwise we could replace primes of order e_i with primes of odd exponent f_i such that f_i divides e_i. Consider modulus m = 64. There is only one covering set, consisting of all the primes dividing 2⁶⁴ - 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 < 10⁸, 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 < 10⁸, we have the following flipping pairs, using label numbers and giving a flip offset.

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 (p_i, m- r_i) as the flip congruences instead of

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

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

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 :

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.