Properties [of substitution systems]
The examples shown here all appear in quite a number of different contexts in this book. Note that each of them in effect yields a single sequence that gets progressively longer at each step; other rules make the colors of elements alternate on successive steps.
(a) (Successive digits sequence) The sequence produced is repetitive, with the element at position n being black for n odd and white for n even. There are a total of 2t elements after t steps. The complete pattern formed by looking at all the steps together has the same structure as the arrangement of base 2 digits in successive numbers shown on page 117.
(b) (Thue–Morse sequence) The color s[n] of the element at position n is given by 1 - Mod[DigitCount[n - 1, 2, 1], 2]. These colors satisfy s[n_] := If[EvenQ[n], 1 - s[n/2], s[(n + 1)/2]] with s[1] = 1. There are a total of 2t elements in the sequence after t steps. The sequence on step t can be obtained from Nest[Join[#, 1 - #] &, {1}, t - 1]. The number of black and white elements at each step is always the same. All four possible pairs of successive elements occur, though not with equal frequency. Runs of three identical elements never occur, and in general no block of elements can ever occur more than twice. The first 2m elements in the sequence can be obtained from (see page 1081)
(CoefficientList[Product[1 - z2s, {s, 0, m - 1}], z] + 1)/2
The first n elements can also be obtained from (see page 1092)
Mod[CoefficientList[Series[(1 + Sqrt[(1 - 3x)/(1 + x)])/(2(1 + x)), {x, 0, n - 1}], x], 2]
The sequence occurs many times in this book; it can for example be derived from a column of values in the rule 150 cellular automaton pattern discussed on page 885.
(c) (Fibonacci-related sequence) The sequence at step t can be obtained from a[t_] := Join[a[t - 1], a[t - 2]]; a[1] = {0}; a[2] = {0, 1}. This sequence has length Fibonacci[t + 1] (or approximately 1.618t + 1) (see note below). The color of the element at position n is given by 2 - (Floor[(n + 1) GoldenRatio] - Floor[n GoldenRatio]) (see page 904), while the position of the kth white element is given by the so-called Beatty sequence Floor[k GoldenRatio]. The ratio of the number of white elements to black at step t is Fibonacci[t - 1]/Fibonacci[t - 2], which approaches GoldenRatio for large t. For all m ≤ Fibonacci[t - 1], the number of distinct blocks of m successive elements that actually appear out of the 2m possibilities is m + 1 (making it a so-called Sturmian sequence as discussed on page 1084).
(d) (Cantor set) The color of the element at position n is given by If[FreeQ[IntegerDigits[n - 1, 3], 1], 1, 0], which turns out to be equivalent to
If[OddQ[n], Sign[Mod[Binomial[n - 1, (n - 1)/2], 3]], 0, 1]
There are 3t elements after t steps, of which 2t are black. The picture below shows the number of black cells that occur before position n. The resulting curve has a nested form, with envelope n^Log[3, 2].