Iterated run-length encoding

Starting say with {1}

{1} consider repeatedly replacing list

✖

list by (see page 1070)

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

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}}

{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 λⁿ

✖

\!\(\*SuperscriptBox[\(\[Lambda]\),\(n\)]\), where λ ≃ 1.3

✖

λ ≃ 1.3 is the root of a degree 71 polynomial, corresponding to the largest eigenvalue of the transition matrix for the substitution system.