For s[s][k][s[s[s][k]]][k] (case (k)) the size at step t - 7 is given by h[1] = h[2] = h[3] = 12 h[t_] := If[Mod[t, 4]  2, 2, 1] (h[Ceiling[t/2] - 1] + t) + {3, 5, -7, -1} 〚 Mod[t, 4] + 1 〛 Examples with similar behavior are s[s[s][k]][s][s[s][k]] , s[s[s]][s][s[s][k]][k] and s[s[s][s]][s][s[s][k]] .

When m itself divides k , the cellular automaton rule is {_, b_, c_}  m Mod[b, k/m] + Quotient[c, k/m] ; in other cases the rule can be obtained by composition.

Starting with a list of the initial conditions for s steps, the configurations for the next s steps are given by Append[Rest[list], Map[Mod[Apply[Plus, Flatten[c #]], 2]&, Transpose[ Table[RotateLeft[list, {0, i}], {i, -r, r}], {3, 2, 1}]]] where r = (Length[First[c]] - 1)/2 .

Such phase changes can be produced by repeatedly applying a single irrational rotation, and using the fact that Mod[h s, 2 π] will eventually for some s come close to any given phase (see page 903 ). … But these correspond to periodicities in the list Mod[a^Range[m], m] . … But now if one sets up a superposition of all these configurations, one can compute Mod[a # , m]& , then essentially use Fourier to find periodicities—all with a polynomial number of quantum gates.

If the values of the cells in each block are labelled p , q and r , then rule 110 can be written as Mod[(1+p) q r + q + r, 2] or And[Not[And[p, q, r]], Or[q, r]].

In general the density for an arrangement of white squares with offsets v is given in s dimensions by (no simple closed formula seems to exist except for the 1 × 1 case) Product[With[{p = Prime[n]}, 1 - Length[Union[Mod[v, p]]]/p s ], {n, ∞ }] White squares correspond to lattice points that are directly visible from the origin at the top left of the picture, so that lines to them do not pass through any other integer points.

(The presence of nested structure is particularly evident in FoldList[Plus, 0, Table[Mod[h n, 1] - 1/2, {n, max}]] .)

And in practice the n th digit can be found just by computing slightly over n terms of the sum, according to Round[FractionalPart[ Sum[FractionalPart[PowerMod[2, n - k, k]/k], {k, n}] + Sum[2 n - k /k, {k, n + 1, n + d}]]] where several values of d can be tried to check that the result does not change.

Block cellular automata With a rule of the form {{1, 1}  {1, 1}, {1, 0}  {1, 0}, {0, 1}  {0, 0}, {0, 0}  {0, 1}} the evolution of a block cellular automaton with blocks of size n can be implemented using BCAEvolveList[{n_Integer, rule_}, init_, t_] := FoldList[BCAStep[{n, rule}, #1, #2]&, init, Range[t]] /; Mod[Length[init], n]  0 BCAStep[{n_, rule_}, a_, d_] := RotateRight[ Flatten[Partition[RotateLeft[a, d], n]/.rule], d] Starting with a single black cell, none of the k = 2 , n = 2 block cellular automata generate anything beyond simple nested patterns.

The sequence Mod[Fibonacci[n], k] is always purely repetitive; the maximum period is 6k , achieved when k = 10 5 m (compare page 975 ). Mod[Fibonacci[n], n] has the fairly complicated form shown below.