Maximum periods [in cellular automata]

A cellular automaton with n cells and k colors has k^{n} possible states, but if the system has cyclic boundary conditions, then the maximum repetition period is smaller than k^{n}. 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^{n} - k. For large n, s[n, k] oscillates between about k^{n} - k^{n/2} and k^{n} - k. (See page 963.)