Somewhat related to the curves shown here is the function MoebiusMu[n] , equal to 0 if n has a repeated prime factor and otherwise (-1)^Length[FactorInteger[n]] . The quantity FoldList[Plus, 0, Table[MoebiusMu[i], {i, n}]] behaves very much like a random walk.

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] .

Unlike for continuous mathematical functions, known algorithms for number theoretical functions such as FactorInteger[x] or MoebiusMu[x] typically seem to require a number of operations that grows faster with the number of digits n in x than any power of n (see page 1090 ).