Block frequencies [in sequences]

In any repetitive sequence the number of distinct blocks of length m must become constant with m for sufficiently large m. In a nested sequence the number must always continue increasing roughly linearly, and must be greater than m for every m. (The differences of successive numbers themselves form a nested sequence.) If exactly m + 1 distinct blocks occur for every m, then the sequence must be of the so-called Sturmian type discussed on page 916, and the n^th element must be given by Round[(n + 1) a + b] - Round[n a + b], where a is an irrational number. Up to limited m nested sequences can contain all k^m possible blocks, and can do so with asymptotically equal frequencies. Pictures (b), (c) and (d) show the simplest cases where this occurs (for length 3 {1  {1, 1, 1, 0, 0, 0}, 0  {1, 0}} also works). Linear feedback shift registers of the type used in picture (e) are discussed below. Concatenation sequences of the type used in picture (f) are discussed on page 913. In both cases equal frequencies of blocks are obtained only for sequences of length exactly 2^j.