The positions of the black cells are given by (and this establishes the connection with the picture on page 117 ) Fold[Flatten[{#1 - #2, #1 + #2}] &, {0}, 2^DigitPositions[t]] DigitPositions[n_] := Flatten[Position[Reverse[IntegerDigits[n, 2]], 1]] - 1 The actual pattern generated by rule 90 corresponds to the coefficients in PolynomialMod[Expand[(1/x + x) t ], 2] (see page 1091 ); the color of a particular cell is thus given by Mod[Binomial[t, (n + t)/2], 2] /; EvenQ[n + t] . Mod[Binomial[t, n], 2] yields a distorted pattern that is the one produced by rule 60 (see page 58 ).

This was for example done by Julia Robinson in 1949 with Δ (or a + 1 ) and Mod[a, b]  0 . And in the 1990s Ivan Korec and others showed that it could be done just with Mod[Binomial[a + b, a], k] with k = 6 or any product of primes—and that it could not be done with k a prime or prime power.

Implementation [of repetitive array] The color of a cell at position {x, y} in the pattern shown is given by Extract[{{1, 0, 1}, {0, 1, 0}}, Mod[{y, x}, {2, 3}] + 1] .

{i[r_]  Table[n + j p  (1 + n Prime[r] (-n + #) &), {j, 0, g - 1}], d[r_, k_]  Table[n + j p  If[Mod[j, Prime[r]]  0, -1 + k + (-n + #)/Prime[r] &, # + 1 &], {j, 0, g - 1}]}] &, prog]]]}] The rules for the arithmetic system are represented so that the system from page 122 becomes for example {2, {0  (3 #/2 &), 1  (3 (# + 1)/2 &)}} . … The evolution of the arithmetic system is given by ASEvolveList[{n_, rules_}, init_, t_] := NestList[(Mod[#, n] /. rules)[#] &, init, t] Given a value m obtained in the evolution of the arithmetic system, the state of the register machine to which it corresponds is {Mod[m, p] + 1, Map[Last, FactorInteger[ Product[Prime[i], {i, nr}] Quotient[m, p]]] - 1} Note that it is possible to have each successive step involve only multiplication, with no addition, at the cost of using considerably larger numbers overall.

The sequence Mod[3 n , 2 s ] obtained from the rightmost s digits corresponds to a simple linear congruential pseudorandom number generator. … (Note that in the particular case used here, pairs of numbers Mod[{3 n , 3 n + 1 }, 2 s ] always lie on lines; with multipliers other than 3, such regularities may occur for longer blocks of numbers.) Note that if one uses base 6 rather than base 2, then as shown on page 614 powers of 3 still yield a complicated pattern, but all operations are strictly local, and the system corresponds to a cellular automaton with 6 possible colors for each cell and rule {a_, b_, c_}  3 Mod[b, 2] + Floor[c/2] (see page 1093 ).

But it is also possible to define this function in an algebraic way f[p_, q_, r_] := Mod[p + r, 2] Algebraic definitions can also be given for other rules: • Rule 254 (page 24 ): 1 - (1 - p)(1 - q)(1 - r) • Rule 250 (page 25 ): p + r - p r • Rule 30 (page 27 ): Mod[p + q + r + q r, 2] • Rule 110 (page 32 ): Mod[(1 + p) q r + q + r, 2] In these definitions, we represent the values of cells by the numbers 1 or 0. … And in this case cellular automaton rules become logic expressions: • Rule 254: Or[p, q, r] • Rule 250: Or[p, r] • Rule 90: Xor[p, r] • Rule 30: Xor[p, Or[q, r]] • Rule 110: Xor[Or[p, q], And[p, q, r]] (Note that Not[p] corresponds to 1 - p , And[p, q] to p q , Xor[p, q] to Mod[p + q, 2] and Or[p, q] to Mod[p q + p + q, 2] .)

The value at step t in the column immediately adjacent to the center is the nested sequence discussed on page 892 and given by Mod[IntegerExponent[t, 2], 2] . The cell at position n on row t turns out to be given by Mod[GegenbauerC[n, -t, -1/2], 2] , as discussed on page 612 .

Cyclic multiplication With multiplication by k at each step the dot will be at position Mod[k t , n] after t steps. If k and n have no factors in common, there will be a t for which Mod[k t , n]  1 , so that the dot returns to position 1.

There are Ceiling[a/2] + Ceiling[2 a/3] - (a + 1) solutions, the one with smallest x being {Mod[2 a + 2, 3] + 1, 2 Floor[(2a + 2)/3] - (a + 2)} . … Writing a in terms of distinct factors as r s , {r + s, r - s}/2 gives a solution if it yields integers—which happens when Abs[a] > 4 and Mod[a, 4] ≠ 2 . • x 2  a y 2 + 1 (Pell equation). … Any solution to the difficult case x 3 + y 3  z 3 - 3 must have Mod[x, 9]  Mod[y, 9]  Mod[z, 9] .

[Turing] machine 596440 For any list of initial colors init , it turns out that successive rows in the first t steps of the compressed evolution pattern turn out to be given by NestList[Join[{0}, Mod[1 + Rest[FoldList[Plus, 0, #]], 2], {{0}, {1, 1, 0}} 〚 Mod[Apply[Plus, #], 2] + 1] 〛 &, init, t] Inside the right-hand part of this pattern the cell values can then be obtained from an upside-down version of the rule 60 additive cellular automaton, and starting from a sequence of 1 's the picture below shows that a typical rule 60 nested pattern can be produced, at least in a limited region.