McCauley Cycles
Suppose we wish to arrange a string of 8 bits in a circle such that
every possible 3-bit string occurs exactly once. One possible
solution is 00011101, which (with wrap-around) gives the eight
sequences of 3 bits
000 001 011 111 110 101 010 100
0 1 3 7 6 5 2 4
Notice that each of the eight numbers in this sequence must be given
by shifting the preceding number one bit to the left (i.e., multiplying
by 2), adding either 0 or 1, and truncating the most significant bit
(i.e., taking the residue modulo 8). Thus, beginning with x=0, each
succeeding number in the sequence is given by either 2x (mod 8) or
2x+1 (mod 8). We can express the above solution just in terms of the
sequence of eight residues 0,1,3,7,6,5,2,4. There is only one other
solution (up to rotations), namely, 0,1,2,5,3,7,6,4, corresponding to
the string 00010111. These two solutions are just the reflections of
each other (up to rotation). Obviously the sequence of bits represents
the summand b in the operation 2x+b (mod 8) at each step, and this is
also the sequence of odd/even numbers in the result.
Joe McCauley noted that we can find analogous sequences modulo any
even number n (not necessarily a power of 2), such that every residue
modulo n appears exactly once, and each number is either 2x (mod n)
or 2x+1 (mod n) relative to the preceding number x. Of course, if n
is not a power of 2, the evaluations modulo n will not be pure
truncations, so these solutions don't correspond exactly to strings
of binary bits taken k bits at a time as they do when n equals 2^k.
To illustrate, the seven solutions for n=14 are
0 1 2 4 8 3 6 13 12 11 9 5 10 7
0 1 2 4 9 5 10 6 13 12 11 8 3 7
0 1 2 4 9 5 11 8 3 6 13 12 10 7
0 1 2 5 10 6 13 12 11 9 4 8 3 7
0 1 2 5 11 9 4 8 3 6 13 12 10 7
0 1 3 6 13 12 11 8 2 4 9 5 10 7
0 1 3 6 13 12 11 9 4 8 2 5 10 7
There are no solutions for odd n. The number of solutions for even
values of n from 2 to 64 are listed below:
# of # of
n solutions n solutions
--- --------- --- ---------
2 1 34 3825
4 1 36 5376
6 1 38 13797
8 2 40 24576
10 3 42 27783
12 4 44 95232
14 7 46 182183
16 16 48 262144
18 21 50 629145
20 48 52 1290240
22 93 54 1835001
24 128 56 3670016
26 315 58 9256395
28 448 60 11059200
30 675 62 28629151
32 2048 64 67108864
As McCauley noted, the numbers of solutions alternate between odd and
even, i.e., the number of solutions is odd if and only if n/2 is odd.
He asked if there are any other patterns in these numbers, and if
there is any other way of producing them. It turns out that there
is. First, here are a few more observations on the table. Letting
f(n) denote the number of cycles of size n, it appears that
f(2(2n)) = 2^(n-1) f(2n) for all n
For example, f(36) = 256 f(18). So this takes care of f(n) all n
divisible by 4, and we only need to determine the values of f(n) for
n = 2k where k is odd. Notice that if n=2p for a prime p then we
usually have
f(2p) = (2^[p-1] - 1)/(p) for p=3,5,11,13,19,29
Of course, by Fermat's theorem, we're assured this quantity is an
integer for any prime p. For example,
f(2*11) = (2^11 - 2)/(2*11) = 93
However, this doesn't cover the primes 7, 17, 23, or 31. These are
precisely the primes (in the range of your table) for which f(2p) is
divisible by p itself. Moreover, for each of these four primes the
value of f(2p) is of the form pm^2. In other words, f(2p)/p is a
square. Furthermore, in three of these cases (p = 7, 17, and 23) we
find that
f(2p) = pm^2 = (2^p - 2)/(2p) - 2m
so we can solve for m to give m = (2^[(p-1)/2]-1)/p, which implies
(2^[(p-1)/2] - 1)^2
f(2p) = --------------------- for p=7,17,23
p
The only remaining prime case (in the table) is p=31, for which we
have f(2*31) = 31^5 = 31(31^2)^2. This looks like kind of an unusual
case, possibly related to the fact that 2^[(31-1)/3)]-1 = (31+2)(31).
Similarly, the values of f(2n) for odd composite n are related to
divisors of 2^q - 1 for primes q that divide n.
Here are a few more observations. First, let's adopt the convention
of letting f(n) denote the number of solutions of length 2n, so that
f(n) is defined for every integer n, odd or even. We don't lose
anything this way because, as McCauley noted, there are no solutions
with odd lengths.
So, with this convention, the observations mentioned above can be
summarized as follows:
f(2n) = 2^(n-1) f(n) for all positive integers n
(2^phi(p) - 1)
f(p) = ---------------- for primes p=3,5,11,13,19,29
p
(2^(phi(p)/2) - 1)^2
f(p) = --------------------- for primes p=7,17,23
p
where phi(n) is Euler's totient function. The prime 31 didn't fit
into either of these patterns, but notice that we have
(2^(phi(p)/6) - 1)^6
f(p) = --------------------- for primes p=31,...?
p
so it's tempting to conjecture that f(p) for every prime p is of
the form
(2^(phi(p)/k) - 1)^k
f(p) = ---------------------
p
for some divisor k of phi(p). It would be interesting to classify
all the primes according to their "k values". Anyway, we can go on
from this to note that, for all the prime powers in the table, we have
k
PROD ( 2^phi(p^j) - 1 )
j=1
f(p^k) = ------------------------------- for p=3,5,11..?
p^k
and the analagous formula for primes p=7,17,23,... Also, notice that
for composite products of two odd primes p,q it appears that
f(pq) = f(p) f(q) [ 2^(phi(pq)/2) - 1 ]^2
These formulae cover all the values in the table, but there are no
examples of more complicated composite numbers, so it isn't clear
how this should be generalized. Still, this is an interesting example
of how much structure can be inferred (or at least guessed) about a
combinatorial function strictly from examining its values, without
even considering its definition.
Based on the above, Bill Daly observed that it looks like phi(p)/k
is the order of 2 mod p, i.e., k = phi(p)/order(2,p). This certainly
seems right, and it's commensurate with the basic definition of the
function, which involves cycles generated by iterating x -> 2x (or
2x+1) modulo p. So, putting it all together, we might conjecture
that, for any integer n = 2^k m where m is odd we have
[(2^k-1)m-k]
2 phi(d)/ord(2,d)
f(n) = ------------- PROD (2^ord(2,d) - 1)
m d|m
Also, to cover all integers n, even as well as odd, we could factor
n = 2^k m where m is odd and then write
n-m phi(d)/ord(2,d)
n f(n) = 2 PROD (2^ord(2,d) - 1)
d|m
where n f(n) is really the total number of cycles of length n
(because f(n) was restricted to those beginning with 0, each of
which represents n others by rotation.) So this seems to
give an explicit formula for the numbers of distinct solutions
of length n.
It might appear that we could reduce this to a simple multiplicative
function, but evidently the cross-product terms involving 2^ord(pq) - 1
make it inherently non-multiplicative. Still, it's an interesting
definition based on the divisors. (I wonder if this can be inverted
using something like the Mobius function.)
This method of generating cyclic sequences can be generalized to
higher orders. For example, instead of considering all cycles
of integers of length n such that each term s[k+1] is either
2s[k] or 2s[k]+1 modulo n, we could allow each term to be of
the form 3s[k], 3s[k]+1, or 3s[k]+2 modulo n. For example, the
four solutions (up to rotation) of length 8 are
0 1 4 6 3 2 7 5
0 2 7 6 3 1 4 5
0 1 3 2 7 6 4 5
0 1 4 5 7 6 3 2
Obviously each of these solutions is uniquely characterized by
the sequence of "remainders" modulo 3, so they each correspond
to an integer with those digits in base 3. The numbers of solutions
for n=2 to 15 are listed below:
# of # of
n solutions n solutions
--- --------- --- ---------
2 1 9 24
3 2 10 14
4 2 11 12
5 2 12 64
6 4 13 42
7 4 14 44
8 4 15 512
Recall that with base 2 there were no solutions except when n is
divisible by 2. Now we see that with base 3 there are clearly more
solutions when n is divisible by 3 than when it is not. However,
there do exist solutions in the latter case.
Return to MathPages Main Menu
Сайт управляется системой
uCoz