Notes

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 n^th 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]