# Notes

## Section 2: Elementary Arithmetic

Relation [of powers] to substitution systems

Despite the uniform distribution result in the note above, the sequence Floor[(n + 1) h] - Floor[n h] is definitely not completely random, and can in fact be generated by a sequence of substitution rules. The first m rules (which yield far more than m elements of the original sequence) are obtained for any h that is not a rational number from the continued fraction form (see page 914) of h by

Map[(({0 Join[#, {1}], 1 Join[#, {1, 0}]} &)[Table[0, {# - 1}]]) &, Reverse[Rest[ContinuedFraction[h, m]]]]

Given these rules, the original sequence is given by

Floor[h] + Fold[Flatten[#1 /. #2] &, {0}, rules]

If h is the solution to a quadratic equation, then the continued fraction form is repetitive, and so there are a limited number of different substitution rules. In this case, therefore, the original sequence can be found by a neighbor-independent substitution system of the kind discussed on page 82. For h = GoldenRatio the substitution system is {0 {1}, 1 {1, 0}} (see page 890), for h = 2 it is {0 {0, 1}, 1 {0, 1, 0}} (see page 892) and for h = 3 it is {0 {1, 1, 0}, 1 {1, 1, 0, 1}}. (The presence of nested structure is particularly evident in FoldList[Plus, 0, Table[Mod[h n, 1] - 1/2, {n, max}]].) (See also pages 892, 916, 932 and 1084.)

From Stephen Wolfram: A New Kind of Science [citation]