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 socalled 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
nontrivially. The optimum coverage can be achieved with 8 distinct
subpatterns 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.
www.irvinemclean.com/kellcyc.htm