Digit sequence properties Empirical evidence for the randomness of the digit sequences of √ n , π , etc. has been accumulating since early computer experiments in the 1940s. … A number is said to be "normal" in a particular base if every digit and every block of digits of any length occur with equal frequency. … One based on gradual extension of work by Richard Stoneham from 1971 is that numbers of the form Sum[1/(p n b p n ), {n, ∞ }] for prime p > 2 are normal in base b (for GCD[b, p]  1 ), and are transcendental.

[Computational complexity of] finding outcomes If one sets up a function to compute the outcome after t steps of evolution from some fixed initial condition—say a single black cell in a cellular automaton—then the input to this function need contain only Log[2, t] digits. But if the evolution is computationally irreducible then to find its outcome will involve explicitly following each of its t steps—thereby effectively finding results for each of the 2^Log[2, t] possible arrangements of digits corresponding to numbers less than t .

Multiplication systems [from cellular automata] The rules for the cellular automaton shown here are {{_, 0, 3 | 8}  5, {_, 0, 2 | 7}  8, {_, 1, 4 | 9}  9, {_, 1, 3 | 8}  4, {_, 1, 2 | 7}  8, {_, 10, 4 | 9}  3, {_, 10, 3 | 8}  7, {_, 10, 2 | 7}  2, {5 | 6, 1, 0}  9, {5 | 6, 10, 0}  3, {5 | 6, 1, _}  6, {5 | 6, 10, _}  5, {_, 2 | 3 | 4 | 5, _}  10, {_, 6 | 7 | 8 | 9, _}  1, {_, x_, _}  x} and the initial condition consists of a single 3 surrounded by 0 's. The idea used is that multiplication by 3 can be achieved by scanning digits from right to left, adding to each digit the value of the digit on its immediate right, as well as a carry that can propagate any distance but cannot be larger than 1.

From the previous section we know that any cellular automaton can be emulated by a universal cellular automaton. … Instructions come in from the left, with memory locations specified by addresses consisting of binary digits.

It exhibits a nested structure, and can be obtained as in the pictures below from the evolution of a 2D substitution system, or equivalently from a Kronecker product as in Nest[Flatten2D[Map[# {{1, 1}, {1, -1}} &, #, {2}]] &, {{1}}, s] with Flatten2D[a_] := Apply[Join, Apply[Join, Map[Transpose,a], {2}]] (c) is known as dyadic or Paley order. It is related to (a) by Gray code reordering of the rows, and to (b) by reordering according to (see page 905 ) BitReverseOrder[a_] := With[{n = Length[a]}, a 〚 Map[FromDigits[Reverse[#], 2] &, IntegerDigits[Range[0, n - 1], 2, Log[2, n]]] + 1 〛 ] It is also given by Array[Apply[Times, (-1)^(IntegerDigits[#1, 2, s] Reverse[IntegerDigits[#2, 2, s]])] &, 2^{s,s}, 0] where (b) is obtained simply by dropping the Reverse . … Mathematical connections with harmonic analysis of discrete groups were investigated from the late 1940s.

One starts by converting the list of cell colors at each step to a polynomial FromDigits[list, x] .

for the substitution system that generates a particular nested pattern, and from these construct a procedure for finding the color of a square in the pattern given its position. … The color of any particular square can also be found by feeding the digit sequences of its y and x coordinates to the finite automaton shown. … In these cases, the colors of squares to the left of the center can be found by starting from the light gray state in the finite automaton; the colors of squares to the right can be found by starting from the black state.

by considering digit sequences in which each digit can again have only a discrete set of possible values, typically just 0 and 1. … Starting from a single black cell, what happens in this case is that the gray essentially just diffuses away, leaving in the end a uniform pattern.

An example is the algorithm of Anatolii Karatsuba from 1961 for finding products of n -digit numbers (with n = 2 s ) by operating on their digits in the nested pattern of page 608 (see also page 1093 ) according to First[f[IntegerDigits[x, 2, n], IntegerDigits[y, 2, n], n/2]] f[x_, y_, n_] := If[n < 1, x y, g[Partition[x, n], Partition[y, n], n]] g[{x1_, x0_}, {y1_, y0_}, n_] := With[{z1 = f[x1, y1, n/2], z0 = f[x0, y0, n/2]}, z1 2 2n + (f[x0 + x1, y0 + y1, n/2] - z1 - z0)2 n + z0] Other examples include the fast Fourier transform (page 1074 ) and related algorithms for ListConvolve , the quicksort algorithm for Sort , and many algorithms in fields such as computational geometry. … But particularly from the discoveries in this book, it seems likely that the very fastest algorithms for many kinds of problems will not in the end have the type of regular structure that characterizes almost all algorithms currently used.

A somewhat related source of nesting relevant in many mathematical systems is the nested pattern formed by the digit sequences of successive numbers, as illustrated on page 117 . But in general nesting need not just arise from larger elements being broken down into smaller ones: for as we have discovered in this book it can also arise when larger elements are built up from smaller ones—and indeed I suspect that this is its more common origin in nature. … Can nesting also arise from these?