A typical kind of failure, illustrated in the pictures on the next page , is that points with coordinates determined by successive numbers from the generator turn out to be distributed in an embarrassingly regular way. … But although some aspects of the behavior of such systems can be made quite random, deviations from perfect randomness are still often found. … Patterns of digits in base 2 produced by starting with the number 1 and then repeatedly multiplying by various fixed constants.

Leading digits [in numbers] In base b the leading digits of powers are not equally probable, but follow the logarithmic law from page 914 .

Indeed, in the end, despite some confusing suggestions from traditional mathematics, we will discover that the general behavior of systems based on numbers is very similar to the general behavior of simple programs that we have already discussed. … But if one looks not at these overall sizes, but rather at digit sequences, then what one sees is considerably more complicated. … Digit sequences of successive numbers written in base 2.

[No text on this page] Fluctuations in the overall increase of sequences from the previous page . In cases (c) and (d), the fluctuations have a regular nested form, and turn out to be directly related to the base 2 digit sequence of n .

But it can also be viewed as a system based on numbers, in which successive rows are the base 10 digit sequences of successive powers of 2. And it turns out that there is a fast way to compute row n just from the base 2 digit sequence of n , as the pictures on the right illustrate. This procedure is based on the standard repeated squaring method of finding 2 n by starting from 2, and then successively squaring the numbers one gets, multiplying by 2 if the corresponding base 2 digit in n is 1.

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 .

Nested digit sequences The number obtained from the substitution system {1  {1, 0}, 0  {0, 1}} is approximately 0.587545966 in base 10. … From the result on page 890 , the number whose digits are obtained from {1  {1, 0}, 0  {1}} is given by Sum[2^(-Floor[n GoldenRatio]), {n, ∞ }] . … The fact that nested digit sequences do not correspond to algebraic numbers follows from work by Alfred van der Poorten and others in the early 1980s.

As we first saw on page 119 , the patterns of digits obtained in this way seem quite random. … For practical reasons, such generators typically keep only, say, the rightmost 31 digits in the numbers at each step. … But in practice over the years, one after another linear congruential generator that has been constructed to have maximal repetition period has turned out to exhibit very substantial deviations from perfect randomness.

[No text on this page] Network systems in which the rule depends on the number of distinct nodes reached by going up to distance two away from each node. … In case (c), it is nested—the size of the network at step t is related to the number of 1's in the base 2 digit sequence of t .

Instead, just as in other examples in this book, the randomness arises from an intrinsic process that occurs even with the simple repetitive initial condition shown in pictures (c) and (d) above. … The point is that the presence of randomness makes the system behave on different steps as if it were evolving from slightly different initial conditions. But statistical averages over different initial conditions typically yield essentially the results one would get by evolution from a single initial condition containing an infinite number of randomly chosen digits.