Further Variants of the “Look-and-Say” Sequence
In two previous posts, I explored Conway’s famous “look-and-say” sequence 1, 11, 21, 1211, 111221, 312211, …, obtained by repeatedly describing the sequence’s previous term, as well as a simple binary variant of the sequence. In this post I will use similar techniques to explore some further variations of the sequence – a version where each term in the sequence is read in ternary, and a related sequence where no digit larger than 2 may be used when describing its terms.
As with the regular look-and-say sequence, the way we will attack these sequences is by constructing a “periodic table” of elementary non-interacting subsequences that all terms in the sequence are made up of. Then standard recurrence relation techniques will allow us to determine the rate of growth of the length of the terms in the sequences as well as the limiting distribution of the different digits in the sequence.
The Ternary Look-and-Say Sequence
Since we have already looked at the regular (i.e., decimal) look-and-say sequence, which is equivalent to the base-4 version of the sequence since it never contains a digit of 4 or larger, and we have also looked at the binary version of the sequence, it makes sense to ask what happens in the intermediate case of the ternary (base-3) version of the sequence: 1, 11, 21, 1211, 111221, 1012211, … (see A001388).
As always, we begin by listing the noninteracting subsequences that make this version of the sequence tick. Not surprisingly, it is more complicated than the corresponding table (of 10 subsequences) in the binary case, but not as complicated as the corresponding table (of 92 subsequences) in the decimal case.
# | Subsequence | Evolves Into |
---|---|---|
1 | 1 | (3) |
2 | 10 | (5) |
3 | 11 | (19) |
4 | 110 | (21) |
5 | 1110 | (2)(4) |
6 | 111210 | (2)(8) |
7 | 111221 | (2)(16) |
8 | 1121110 | (22)(4) |
9 | 112211 | (23) |
10 | 112221 | (21)(20) |
11 | 11222110 | (21)(24) |
12 | 1122211210 | (21)(25) |
13 | 1211 | (7) |
14 | 121110 | (6)(4) |
15 | 1221 | (9) |
16 | 12211 | (10) |
17 | 122110 | (11) |
18 | 1221121110 | (12)(4) |
19 | 21 | (13) |
20 | 211 | (15) |
21 | 2110 | (17) |
22 | 211210 | (18) |
23 | 212221 | (14)(20) |
24 | 22110 | (26) |
25 | 221121110 | (27)(4) |
26 | 222110 | (2)(24) |
27 | 22211210 | (2)(25) |
The (27×27) transition matrix for this evolution rule is included in the text file at the end of this post. Its characteristic polynomial is
The maximal eigenvalue of the transition matrix is thus the largest root of x3 – x – 1, which is approximately 1.324718. It follows that the number of digits in the terms of this sequence grows on average by about 32.5% from one term to the next.
The Look-and-Say Sequence with Digits 1 and 2
Closely related to the ternary version of the sequence is the sequence obtained by reading the previous term in the sequence, but with the restriction that you can never use a number larger than 2 (see A110393). This sequence begins 1, 11, 21, 1211, 111221, 21112211, …, and the sixth term is obtained by reading the fifth term as “two ones, one one, two twos, one one”. Because only two different digits appear in this sequence, it is perhaps not surprising that its table of noninteracting subsequences is quite simple:
# | Subsequence | Evolves Into |
---|---|---|
1 | 1 | (2) |
2 | 11 | (5) |
3 | 111 | (7) |
4 | 1211 | (3)(6)(1) |
5 | 21 | (4) |
6 | 22 | (6) |
7 | 2111 | (1)(6)(3) |
The transition matrix associated with this evolution rule is
As before, the average rate of growth of the number of digits in the terms of this sequence is determined by the magnitude of the largest eigenvalue of this matrix. A simple calculation reveals that this eigenvalue is √φ = 1.272…, where φ = (1 + √5)/2 is the golden ratio. Furthermore, we can answer the question of how many 1s there are in the terms of this sequence compared to 2s by looking at the eigenvector corresponding to the maximal eigenvalue:
What this means is, for example, that the second elementary subsequence (11) occurs φ times as frequently as the fourth elementary subsequence (1211). By weighting the subsequences by the entries in this vector appropriately, we can calculate the limiting ratio of the number of ones to the number of twos as
Download: Transition matrices [plaintext file]
Recent Comments