Chapter 4: Systems Based on Numbers

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=Sqrt[2] it is {0->{0,1}, 1->{0,1,0}} (see page 892) and for h=Sqrt[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]