For every covering set P, there is a finite number of Keller cycles, since they are calculated mod 2P

Joseph McLean

Identifying Keller cycles

For every covering set P, there is a finite number of Keller cycles, since they are calculated mod 2P. For Sierpinski modulus m = 24, there is one covering set, which is known to have 2 associated Keller cycles. Each of the 4 distinct covering sets of modulus 36 has 4 different Keller cycles. However, the size of 2P increases substantially for higher modulii, and so it is next to impossible to identify how many Keller cycles there are based on observation.

I have previously noted that covering set X = {3, 5, 7, 11, 13, 31, 41, 61, 151} has a noticeably high number of associated Keller cycles, not all currently identified, and it would be of interest if an explanation were available.

It occurred to me that the number of Keller cycles must be related to the exact covering arrangement, i.e. the set of Nash congruences., since it is this set which dictates the values in the cycle.

N.B. For detailed definitions of the concepts of covering sets, Keller cycles, flip cycles, Nash congruences, etc. see the reports of my previous investigations into Sierpinski numbers (see reference1, reference2, reference3).

Consider the smallest covering set A = {3, 5, 7, 13, 17, 241} of modulus 24. The exponents to the base 2 of the primes are: 2, 4, 3, 12, 8 & 24 respectively. It is obvious that first three primes must be arranged as in the divisibility grid below (subject to cycling), since any other arrangement will leave too many holes for the remaining primes to cover.

0	1	2	3	4	5	6	7	8	9	10	11
3	7	3	5	3, 7		3	7, 5	3		3, 7	5
12	13	14	15	16	17	18	19	20	21	22	23
3	7	3	5	3, 7		3	7, 5	3		3, 7	5

The corresponding Nash congruences are (3,0); (5,3) and (7,1), leaving holes at positions 5, 9, 17 & 21. The prime 13 can cover either positions 5 & 17 or positions 9 & 21, leaving the last two primes to cover the last two holes. Since we can cycle round the positions, it doesn’t matter which way round these last two go. This leaves us with 2 possible sets of Nash congruences:

(3,0); (5,3); (7,1); (13,5); (17,9); (241,21) and

(3,0); (5,3); (7,1); (13,9); (17,5); (241,17)

If we convert to the Sierpinski congruences this provides:

(3,1); (5,1); (7,6); (13,4); (17,16); (241,225) and

(3,1); (5,1); (7,6); (13,10); (17,1); (241,226)

The solutions of the simultaneous congruences provide values which can be cycled to 271129 & 271577 respectively, which are our two seed values for the two known Keller cycles for this covering set. The obvious rotational symmetry of the patterns also indicates that the two cycles are flip cycles of each other.

Note that we could have proceeded above by using the prime 17 first, which could cover positions 5 & 21 or positions 9 & 17, before including 13 and 241 to cover the last two holes, but this would have provided the same two arrangements subject to cycling.

We can proceed analogously for other covering sets, for instance B = {3, 5, 7, 13, 19, 37, 73} with exponents 2, 4, 3, 12, 18, 36, 9 respectively. The first three primes must take up the following relative arrangement as before.

0	1	2	3	4	5	6	7	8
3	7	3	5	3, 7		3	7, 5	3
9	10	11	12	13	14	15	16	17
	3, 7	5	3	7	3	5	3, 7
18	19	20	21	22	23	24	25	26
3	7, 5	3		3, 7	5	3	7	3
27	28	29	30	31	32	33	34	35
5	3, 7		3	7, 5	3		3, 7	5

This leaves 6 holes at positions 5, 9, 17, 21, 29 & 35. Since 5, 17 & 29 differ by 12, it is convenient to consider using the prime 13 first. This leaves 3 holes for 3 primes. Subject to cycling, the only two distinct arrangements occur using either 19, 37 & 73 or 19, 73 & 37 in order, giving two sets of Nash congruences:

(3,0); (5,3); (7,1); (13,5); (19,9); (37,21); (73,33)

(3,0); (5,3); (7,1); (13,5); (19,9); (37,33); (73,21)

Alternatively, since the cycle pattern at positions 9, 21 & 33 is different (consider the primes in the adjacent boxes), if we use the prime 13 to cover these three points, then we get another two distinct arrangements, with associated Nash congruences:

(3,0); (5,3); (7,1); (13,9); (19,5); (37,17); (73,29)

(3,0); (5,3); (7,1); (13,9); (19,5); (37,29); (73,17)

These 4 sets of Nash congruences are the only ones possible, and lead directly to the four known Keller cycles for covering set B, namely, and in order, 78557 (1.0), 12756019 (19.0), 8184977 (13.0) & 2510177 (9.0).

Looking closely at the actual divisibility pattern, we can see that the second two arrangements are just the flip cycles of the first two.

Now we can turn to covering set X = {3, 5, 7, 11, 13, 31, 41, 61, 151} again, with corresponding exponents 2, 4, 3, 10, 12, 5, 20, 60 & 15, and Sierpinski modulus 60. We use the first three primes in the same manner, as indicated below.

0	1	2	3	4	5	6	7	8	9
3	7	3	5	3, 7		3	7, 5	3
10	11	12	13	14	15	16	17	18	19
3, 7	5	3	7	3	5	3, 7		3	7, 5
20	21	22	23	24	25	26	27	28	29
3		3, 7	5	3	7	3	5	3, 7
30	31	32	33	34	35	36	37	38	39
3	7, 5	3		3, 7	5	3	7	3	5
40	41	42	43	44	45	46	47	48	49
3, 7		3	7, 5	3		3, 7	5	3	7
50	51	52	53	54	55	56	57	58	59
3	5	3, 7		3	7, 5	3		3, 7	5

There are 10 holes remaining. The prime 13 can take out 5 holes on its own, leaving 5 primes for 5 holes. Additionally, the pattern at position 5 is different from the pattern at position 9, so there are two possible congruence positions for prime 13. Ignoring cycling, 5 objects can be ordered in 24 different ways, which provides us with 48 different Keller cycles. Let us calculate them.

We already have the Nash congruences (3,0); (5,3) & (7,1). With prime 13 at position 5, we can without loss of generality always take prime 11 at position 9, and permuting the other four primes to cover positions 21, 33, 45 & 57 gives congruences and Keller cycles as follows:

Prime	31	41	61	151	Keller base	Code
positions	21	33	45	57	8828557967
	33	45	57	21	7654214851
	45	57	21	33	6074506667
	57	21	33	45	3352744951
	21	45	33	57	1156418821	93
	45	33	57	21	292099127	48
	33	57	21	45	8732742857
	57	21	45	33	5910942259
	21	57	33	45	839316707	78
	57	33	45	21	12863336191
	33	45	21	57	13526019167
	45	21	57	33	3130169719
	21	45	57	33	488303521	59
	45	57	33	21	12472164799
	57	33	21	45	15416050697
	33	21	45	57	7791902033
	21	33	57	45	1460644561	102
	33	57	45	21	4257162139
	57	45	21	33	6727650317
	45	21	33	57	332320309	51
	21	57	45	33	6704667413
	57	45	33	21	5280400219
	45	33	21	57	3218627963
	33	21	57	45	4369208401

Note that if the position number exceeds the value of the prime, we can just reduce it modulo the exponent of the prime. The so-called Keller base is the smallest value in the Keller cycle, and the code provided pertains to the nomenclature given to the identified cycles during previous searches.

With prime 13 at position 9 we can fix prime 11 at position 5, and use the same set of permutations on the remaining four positions at 17, 29, 41 & 53 to get a different set of Keller cycles:

Prime	31	41	61	151	Keller base	Code
positions	17	29	41	53	3705973519
	29	41	53	17	2861264993
	41	53	17	29	2305843763
	53	17	29	41	710530043	73
	17	41	29	53	297988073	49
	41	29	53	17	1828217513	110
	29	53	17	41	1591804639	106
	53	17	41	29	5224113319
	17	53	29	41	6251263583
	53	29	41	17	497369479	60
	29	41	17	53	15517084189
	41	17	53	29	3580721119
	17	41	53	29	19716471199
	41	53	29	17	6415720099
	53	29	17	41	17359225399
	29	17	41	53	4213998407
	17	29	53	41	17149643633
	29	53	41	17	15096963691
	53	41	17	29	5786077909
	41	17	29	53	6336582061
	17	53	41	29	266142407	46
	53	41	29	17	9696508127
	41	29	17	53	3487626379
	29	17	53	41	9020022259

The 2P value for covering set X is 351566645430, which is too big to reach with an exhaustive search, but no other possible arrangements exist that are essentially distinct from those indicated above.

There are altogether 23 covering sets of Sierpinski modulus 60, of which 21 have the subset {3, 5, 7, 13}, so by the above argument, these will all have at least 48 associated Keller cycles. However, since the remaining members of the others sets are larger than those for set X, the typical Keller base will be larger, explaining why far fewer were revealed during the exhaustive search.

The examples provided so far all have the subset {3, 5, 7, 13}, which nicely covers the great majority of possible positions. Let us now consider a covering set that has neither 7 nor 13. The smallest modulus with covering sets like this is m = 48. The primes 3 & 5 cover 36 between them. The prime 17 can take another 6, and the primes 241 & 257 can fill 2 more each, leaving 2 more primes, namely 97 & 673, to cover the remaining 2 holes. Given the patterns, there are only two distinct arrangements, given by the Nash congruences:

(3,0); (5,1); (17,3); (241,7); (257,15); (97,23); (673,39) &

(3,0); (5,1); (17,3); (241,7); (257,15); (97,39); (673,23)

This solves to the Keller cycles with bases 39803042693 & 17569606849 respectively.

The process outlined above can be applied to any covering set to identify all Keller cycles.

However, it is difficult to identify all possible distinct arrangements when the covering set is large, as in the next example.

The first covering sets which do not include the prime 3 are found for Sierpinski modulus m = 180. The loss of such a useful value (when it is in a covering set it covers half of all holes) can only be made up by relying on lots of other primes with low exponent. An optimal covering arrangement is provided by judicious placement of the primes 7, 5, 31, 73, 11, 13, which can be made to cover 142 of the possible 180 holes. Identifying distinct patterns is quite difficult, but I reckon that there are 8 to this point. The three primes 151, 331 & 19 can then be used to account for another 18 holes. Care has to be taken here since the divisibility patterns of these primes interact non-trivially. The optimum coverage can be achieved with 8 distinct sub-patterns of these three. The 9 primes mentioned so far feature in every covering set of modulus 180 that does not contain the prime 3, of which there are at least 62. A variety of combinations of the remaining primes can be made to cover the remaining positions. The one with the smallest 2P value continues with 41, 37 & 109, each covering 4 holes, 631 & 23311 each covering 2 holes, leaving 61 & 1321 to cover the last 4 holes. The only possible arrangements allow one of these to cover 3 holes while the other finishes off the last hole, again interchangeably. The total number of distinct patterns, leading to distinct Keller cycles, is of the order of 8*8*8 = 512, though this may be a couple of factors of 2 out.