Maximum periods [in cellular automata]

A cellular automaton with n cells and k colors has kⁿ possible states, but if the system has cyclic boundary conditions, then the maximum repetition period is smaller than kⁿ. The reason is that different states of the cellular automaton have different symmetry properties, and thus cannot be on the same cycle. In particular, if a state of a cellular automaton has a certain spatial period, given by the minimum positive m for which RotateLeft[list, m]list, then this state can never evolve to one with a larger spatial period. The number of states with spatial period m is given by

s[m_, k_]:= k^m - Apply[Plus, Map[s[#, k] &, Drop[Divisors[m], -1]]]

or equivalently

s[m_, k_]:=Apply[Plus, (MoebiusMu[m/#] k^# &)[Divisors[m]]]

In a cellular automaton with a total of n cells, the maximum possible repetition period is thus s[n, k]. For k = 2, the maximum periods for n up to 10 are: {2, 2, 6, 12, 30, 54, 126, 240, 504, 990}. In all cases, s[n, k] is divisible by n. For prime n, s[n, k] is kⁿ - k. For large n, s[n, k] oscillates between about kⁿ - k^n/2 and kⁿ - k. (See page 963.)