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}]]. In the limit, such sequences contain with equal frequency all possible blocks of any given length, but as shown on page 597, they exhibit other obvious deviations from randomness. The picture below shows the k = 2 sequence chopped into length 256 blocks.
Applying FoldList[Plus, 0, 2list - 1] to the whole sequence yields the pattern shown below.
The systematic increase is a consequence of the leading 1 in each concatenated sequence. Dropping this 1 yields the pattern below.
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 kn+1 digits of a concatenation sequence can be found fairly efficiently from
k/(k - 1)2 - (k - 1) Sum[k(ks - 1) ((1 + s - s k)/(k - 1)) (1/((k - 1) (ks - 1)2) - k/((k - 1) (ks + 1 - 1)2) + 1/(ks + 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.