Other examples [of substitution systems]

(a) (Period-doubling sequence) After t steps, there are a total of 2^t

\!\(\*SuperscriptBox[\(2\),\(t\)]\) elements, and the sequence is given by Nest[MapAt[1 - # &, Join[#, #], -1]&, {0}, t]

✖

Nest[MapAt[1 - # &, Join[#, #], -1]&, {0}, t]. It contains a total of Round[2^t/3]

✖

Round[\!\(\*SuperscriptBox[\(2\),\(t\)]\)/3] black elements, and if the last element is dropped, it forms a palindrome. The n^th element is given by Mod[IntegerExponent[n, 2], 2]

✖

Mod[IntegerExponent[n, 2], 2]. As discussed on page 885, the sequence appears in a vertical column of cellular automaton rule 150. The Thue–Morse sequence discussed on page 890 can be obtained from it by applying

1 - Mod[Flatten[Partition[FoldList[Plus, 0, list], 1, 2]], 2]

1 - Mod[Flatten[Partition[FoldList[Plus, 0, list], 1, 2]], 2]

(b) The n^th element is simply Mod[n, 2]

Mod[n, 2].

(c) Same as (a), after the replacement 1  {1, 1}

1  {1, 1} in each sequence. Note that the spectra of (a) and (c) are nevertheless different, as discussed on page 1080.

(d) The length of the sequence at step t satisfies a[t]  2a[t - 1] + a[t - 2]

a[t]  2a[t - 1] + a[t - 2], so that a[t] = Round[(1 + √2)^{t - 1}/2]

✖

a[t]=Round[\!\(\*SuperscriptBox[\((1+\!\(\*SqrtBox[\(2\)]\))\),\(t-1\)]\)/2] for t > 1

✖

t > 1. The number of white elements at step t is then Round[a[t]/√2]

✖

Round[a[t]/\!\(\*SqrtBox[\(2\)]\). Much like example (c) on page 83 there are m + 1

✖

m + 1 distinct blocks of length m, and with f = Floor[(1 - 1/√2)(# + 1/√2)] &

✖

f=Floor[(1-1/\!\(\*SqrtBox[\(2\)]\))(#+1/\!\(\*SqrtBox[\(2\)]\))]& the n^th element of the sequence is given by f[n + 1] - f[n]

✖

f[n + 1] - f[n] (see page 903).

(e) For large t the number of elements increases like λ^t

\!\(\*SuperscriptBox[\(\[Lambda]\),\(t\)]\) with λ = (√13 + 1)/2

✖

\[Lambda]=(\!\(\*SqrtBox[\(13\)]\)+1)/2; there are always λ times as many white elements as black ones.

(f) The number of elements at step t is Round[(1 + √2)^t/2]

Round[\!\(\*SuperscriptBox[\((1+\!\(\*SqrtBox[\(2\)]\))\),\(t\)]\)/2], and the n^th element is given by Floor[√2 (n + 1)] - Floor[√2 n]

✖

Floor[\!\(\*SqrtBox[\(2\)]\)(n+1)]-Floor[\!\(\*SqrtBox[\(2\)]\),n] (see page 903).

(g) The number of elements is the same as in (f).

(h) The number of black elements is 2^{t - 1}

\!\(\*SuperscriptBox[\(2\),\(t-1\)]\); the total number of elements is 2^{t - 2} (t + 1)

✖

\!\(\*SuperscriptBox[\(2\),\(t-2\)]\)(t+1).

(i) and (j) The total number of elements is 3^{t - 1}

\!\(\*SuperscriptBox[\(3\),\(t-1\)]\).