Chapter 4: Systems Based on Numbers

Section 2: Elementary Arithmetic

Iterated run-length encoding

Starting say with {1} consider repeatedly replacing list by (see page 1070)

Flatten[Map[{Length[#], First[#]} &, Split[list]]]

The resulting sequences contain only the numbers 1, 2 and 3, but otherwise at first appear fairly random. However, as noticed by John Conway around 1986, the sequences can actually be obtained by a neighbor-independent substitution system, acting on 92 subsequences, with rules such as {3,1,1,3,3,2,2,1,1,3}->{{1,3,2},{1,2,3,2,2,2,1,1,3}}. The system thus in the end produces patterns that are purely nested, though formed from rather complicated elements. The length of the sequence at the nth step grows like λn, where λ1.3 is the root of a degree 71 polynomial, corresponding to the largest eigenvalue of the transition matrix for the substitution system.

From Stephen Wolfram: A New Kind of Science [citation]