Connection [of geometric substitution systems] with digit sequences Patterns after t steps can be viewed as containing all t -digit integers in an appropriate complex base. Thus the patterns on page 189 can be formed from t -digit integers in base  - 1 containing only digits 0 and 1, as given by Table[FromDigits[IntegerDigits[s, 2, t],  - 1], {s, 0, 2 t -1}] In the particular case of base  - q with digits 0 through q 2 , it turns out that for sufficiently large t any complex integer can be represented, and will therefore be part of the pattern.

IntegerDigits[n, 2] . … Starting with an ordinary base 2 digit sequence, one prepends a unary specification of its length, then a specification of that length specification, and so on: (Flatten[{Sign[-Range[1 - Length[#], 0]], #}] &)[ Map[Rest, IntegerDigits[Rest[Reverse[NestWhileList[ Floor[Log[2, #] &, n + 1, # > 1 &]]],2]]] (d) Binary-coded base 3. … Flatten[IntegerDigits[ Append[2 - With[{w = Floor[Log[3, 2n]]}, IntegerDigits[n - (3 w + 1 - 1)/2, 3, w]], 3], 2, 2]] (e) Fibonacci encoding.

Structures [in rule 110] The persistent structures shown can be obtained from the following {n, w} by inserting the sequences IntegerDigits[n, 2, w] between repetitions of the background block b : {{152, 8}, {183, 8}, {18472955, 25}, {732, 10}, {129643, 18}, {0, 5}, {152, 13}, {39672, 21}, {619, 15}, {44, 7}, {334900605644, 39}, {8440, 15}, {248, 9}, {760, 11}, {38, 6}} The repetition periods and distances moved in each period for the structures are respectively {{4, -2}, {12, -6}, {12, -6}, {42, -14}, {42, -14}, {15, -4}, {15, -4}, {15, -4}, {15, -4}, {30, -8}, {92, -18}, {36, -4}, {7, 0}, {10, 2}, {3, 2}} Note that the periodicity of the background forces all rule 110 structures to have periods and distances given by {4, -2} r + {3, 2} s where r and s are non-negative integers. … Extended versions of (b) and (c) can be obtained from Flatten[{IntegerDigits[1468, 2], Table[ IntegerDigits[102524348, 2], {n}], IntegerDigits[v, 2]}] where n is a non-negative integer and v is one of {1784, 801016, 410097400, 13304, 6406392, 3280778648} Note that in most cases multiple copies of the same structure can travel next to each other, as seen on page 290 .

Digit counts The number of black squares on row n in the pattern shown here is given by DigitCount[n, 2, 1] and is plotted below. … Formulas for DigitCount[n, 2, 1] include n - IntegerExponent[n!… Straightforward generalizations of DigitCount can be defined for integer and non-integer bases and by looking not only at the total number of digits but also at correlations between digits.

Specifying an operator f (taken in general to have n arguments with k possible values) by giving the rule number u for f[p, q, …] , the rule number for an expression with variables vars can be obtained from With[{m = Length[vars]}, FromDigits[ Block[{f = Reverse[IntegerDigits[u, k, k n ]] 〚 FromDigits[ {##}, k] + 1 〛 &}, Apply[Function[Evaluate[vars], expr], Reverse[Array[IntegerDigits[# - 1, k, m] &, k m ]], {1}]], k]]

The number of black cells on row t is given by 2^DigitCount[t, 2, 1] , where DigitCount[t, 2, 1] is plotted on page 902 . 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] . … In this pattern, the color of a particular cell can be obtained directly from the digit sequences for t and n by 1 - Sign[BitAnd[-t, n]] or (see page 583 ) With[{d = Ceiling[Log[2, Max[t, n] + 1]]}, If[FreeQ[ IntegerDigits[t, 2, d] - IntegerDigits[n, 2, d], -1], 1, 0]]

Operator representations Instead of repeatedly applying an operation to a sequence of digits one can consider forming integers (or other numbers) by performing trees of operations on a single constant. … In this case 6 is (1 ∘ (1 ∘ 1)) ∘ 1 , and an integer m can be obtained by Tr[1 + IntegerDigits[m, 2]] - 2 or at most Log[2, m] applications of ∘ . … (For BitOr[2a, b] - 1 the number of applications needed is With[{i = IntegerDigits[m, 2]}, Tr[i + 1] + i 〚 2 〛 (1 + i 〚 3 〛 ) - 1] .)

The number of cells that are not white on row t in this case is given by Apply[Times, 1 + IntegerDigits[t, k]] . … A related result is that IntegerExponent[Binomial[t, n], k] is given by the number of borrows in the base k subtraction of n from t . Mod[Binomial[t, n], k] is given for prime k by With[{d = Ceiling[Log[k, Max[t, n] + 1]]}, Mod[Apply[Times, Apply[Binomial, Transpose[ {IntegerDigits[t, k, d] , IntegerDigits[n, k, d] }], {1}]], k]] The patterns obtained for any k are nested.

With offset list os and k colors the possible neighborhood configurations are Reverse[Table[IntegerDigits[i - 1, k, Length[os]], {i, k^Length[os]}]] (These are shown on page 53 for elementary rules and page 941 for 5-neighbor rules.) If a cellular automaton rule takes the new color of a cell with neighborhood configuration IntegerDigits[i, k, Length[os]] to be u 〚 i + 1 〛 , then one can define its rule number to be FromDigits[Reverse[u], k] . A single step in evolution of a general cellular automaton with state a and rule number num is then given by Map[IntegerDigits[num, k, k^Length[os]] 〚 -1 - # 〛 &, Apply[Plus, MapIndexed[k^(Length[os] - First[#2]) RotateLeft[a, #1] &, os]], {-1}] or equivalently by Map[IntegerDigits[num, k, k^Length[os]] 〚 -# - 1 〛 &, ListCorrelate[Fold[ReplacePart[k #1, 1, #2 + r + 1] &, Array[0 &, Table[2r + 1, {d}]], os], a, r + 1], {d}]

In every picture both x and y run from 1 to 127. d[n] stands for IntegerDigits[n, 2, 7] . (h) is equivalent to digit sequences of powers of 3 in base 2 (see page 120 ).