Concatenation sequences One can consider forming sequences by concatenating digits of successive integers in base k , as in Flatten[Table[IntegerDigits[i, k], {i, n}]] . … This is similar to picture (c) on page 131 , and is a digit-by-digit version of FoldList[Plus, 0, Table[Apply[Plus, 2 Rest[IntegerDigits[i, 2]] - 1], {i, n}]] Note that although the picture above has a nested structure, the original concatenation sequences are not nested, and so cannot be generated by substitution systems. The element at position n in the first sequence discussed above can however be obtained in about Log[n] steps using ((IntegerDigits[#3 + Quotient[#1, #2], 2] 〚 Mod[#1, #2] + 1 〛 &)[n - (# - 2)2 # - 1 - 2, #, 2 # - 1 ]&)[NestWhile[# + 1&, 0, (# - 1)2 # + 1 < n &]] where the result of the NestWhile can be expressed as Ceiling[1 + ProductLog[1/2(n - 1)Log[2]]/Log[2]] Following work by Maxim Rytin in the late 1990s about k n+1 digits of a concatenation sequence can be found fairly efficiently from k/(k - 1) 2 - (k - 1) Sum[k (k s - 1) ((1 + s - s k)/(k - 1)) (1/((k - 1) (k s - 1) 2 ) - k/((k - 1) (k s + 1 - 1) 2 ) + 1/(k s + 1 - 1)), {s, n}] Concatenation sequences can also be generated by joining together digits from other representations of numbers; the picture below shows results for the Gray code representation from page 901 .

Computing powers [of numbers] The method of repeated squaring (also known as the binary power method, Russian peasant method and Pingala's method) computes the quantity m t by performing about Log[t] multiplications and building up the sequence FoldList[#1 2 m #2 &, 1, IntegerDigits[t, 2]] (related to the Horner form for the base 2 representation of t ). Given two numbers x and y their product can be computed in base k by ( FromDigits does the carries) FromDigits[ListConvolve[IntegerDigits[x, k], IntegerDigits[y, k], {1, -1}, 0], k] For numbers with n digits direct evaluation of the convolution would take about n 2 steps. … Note that even though one may only want to find a single digit in m t , I know of no way to do this without essentially computing all the other digits in m t as well.

Digit reversal Sequences of the form Table[FromDigits[ Reverse[IntegerDigits[n, k, m]], k], {n, 0, k m - 1}] shown below appear in algorithms such as the fast Fourier transform and, with different values of k for different coordinates, in certain quasi-Monte Carlo schemes.

Implementation [of 2D cellular automata] An n × n array of white squares with a single black square in the middle can be generated by PadLeft[{{1}}, {n, n}, 0, Floor[{n, n}/2]] For the 5-neighbor rules introduced on page 170 each step can be implemented by CAStep[rule_, a_] := Map[rule 〚 10 - # 〛 &, ListConvolve[{{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}, a, 2], {2}] where rule is obtained from the code number by IntegerDigits[code, 2, 10] . For the 9-neighbor rules introduced on page 177 CAStep[rule_, a_] := Map[rule 〚 18 - # 〛 &, ListConvolve[{{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}, a, 2], {2}] where rule is given by IntegerDigits[code, 2, 18] . In d dimensions with k colors, 5-neighbor rules generalize to (2d + 1) -neighbor rules, with CAStep[{rule_, d_}, a_] := Map[rule 〚 -1 - # 〛 &, a + k AxesTotal[a, d], {d}] AxesTotal[a_, d_] := Apply[Plus, Map[RotateLeft[a, #] + RotateRight[a, #]&, IdentityMatrix[d]]] with rule given by IntegerDigits[code, k, k(2d(k - 1) + 1)] . 9-neighbor rules generalize to 3 d -neighbor rules, with CAStep[{rule_, d_}, a_] := Map[rule 〚 -1 - # 〛 &, a + k FullTotal[a, d], {d}] FullTotal[a_, d_] := Array[RotateLeft[a, {##}] &, Table[3, {d}], -1, Plus] - a with rule given by IntegerDigits[code, k, k((3 d - 1)(k - 1) + 1)] .

Implementation of digit sequences A whole number n can be converted to a sequence of digits in base k using IntegerDigits[n,k] or (see also page 1094 ) Reverse[Mod[NestWhileList[Floor[#/k] &, n, # ≥ k &], k]] and from a sequence of digits using FromDigits[list,k] or Fold[k #1 + #2 &, 0, list] For a number x between 0 and 1, the first m digits in its digit sequence in base k are given by RealDigits[x, k, m] or Floor[k NestList[Mod[k #, 1]&, x, m - 1]] and from these digits one can reconstruct an approximation to the number using FromDigits[{list, 0}, k] or Fold[#1/k + #2 &, 0, Reverse[list]]/k

The number of steps for which a cell at position n will survive can be computed as Module[{q = n + k - 1, s = 1}, While[Mod[q, k] ≠ 0, q = Ceiling[(k - 1)q/k]; s++]; s] If a cell is going to survive for s steps, then it turns out that this can be determined by looking at the last s digits in the base k representation of its position. For k = 2 , a cell survives for s steps if these digits are all 0 (so that s  IntegerExponent[n, k] ). … The solution is Fold[Mod[#1 + k, #2, 1]&, 0, Range[n]] , or FromDigits[RotateLeft[IntegerDigits[n, 2]], 2] for k = 2 .

Properties of [recursive] sequences Sequence (d) is given by f[n_] := (n + g[IntegerDigits[n, 2]])/2 g[{1 ..}] = 1; g[{1, 0 ..}] = 0 g[{1, s__}] := 1 + g[IntegerDigits[FromDigits[{s}, 2] + 1, 2]] The list of elements in the sequence up to value m is given by Flatten[Table[Table[n, {IntegerExponent[n, 2] + 1}], {n, m}]] The differences between the first 2 (2 k -1) of these elements is Nest[Replace[#, {x___}  {x, 1, x, 0}]&, {}, k] The largest n for which f[n]  m is given by 2m + 1 - DigitCount[m, 2, 1] or IntegerExponent[(2m)!… Hump m in the picture of sequence (c) shown is given by FoldList[Plus, 0, Flatten[Nest[Delete[NestList[Rest, #, Length[#] - 1], 2]&, Append[Table[1, {m}], 0], m]] - 1/2] The first 2 m elements in the sequence can also be generated in terms of reordered base 2 digit sequences by FoldList[Plus, 1, Map[Last[Last[#]]&, Sort[Table[{Length[#], Apply[Plus, #], 1 - #}& [ IntegerDigits[i, 2]], {i, 2 m }]]]] Note that the positive and negative fluctuations in sequence (f) are not completely random: although the probability for individual fluctuations in each direction seems to be the same, the probability for two positive fluctuations in a row is smaller than for two negative fluctuations in a row.

[Subset of] elementary rules The examples shown have rule numbers n for which IntegerDigits[n, 2, 8] matches {_, i_, _, j_, i_, _, j_, 0} .

Reversible mobile automata can for instance be constructed using Table[(IntegerDigits[i, 2, 3]  If[First[#]  0, {#, -1}, {Reverse[#], 1}]&)[IntegerDigits[perm 〚 i 〛 , 2, 3]], {i, 8}] where perm is an element of Permutations[Range[8]] .

Numbering scheme [for 2D constraints] The constraint numbered n allows the templates at Position[IntegerDigits[n, 2, 32], 1] in the list below.