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]
You might be interested of a visualization I made of the (standard) look and say sequence, using a walk on the square lattice to represent a sequence.
@Alexandre Owen Muñiz – Very nice, thanks for sharing! I expect that if a similar procedure were performed for the common variants of the look-and-say sequence, the patterns in the walk would be much more apparent due to the smaller number of elementary subsequences (so the walk would basically be made up of 10 or so different components repeated in slightly varying order, rather than 92 such components).
Still some questions, how do we determine the list of the noninteracting subsequences? Is there a methode that we can calculate by hand or we have to ask the computer for help?And are they unique? In your opinion, the look-and-say sequence,can it just be a mathematical puzzle or it can be used in practical? If yes, what’s its applications? thanks a lot
@Fangyan – Conway found the 92 basic subsequences for the original Look-and-Say sequence via computer search. Another, very well-documented, computer search to repeat this calculation was carried out here.
The basic subsequences for the variants that I looked at were all found by hand (just by looking guessing, and then later verifying that they worked). I tried to find the basic subsequences for the roman numeral variant of the sequence by hand, but failed — perhaps a computer search could solve that problem.
I expect that there is a unique minimal set of basic subsequences, but honestly that’s nothing more than a gut feeling — I could be very wrong.
As for practical applications of the look-and-say sequence, I have no idea. I like it just because it’s a fun puzzle that doesn’t even seem mathematical at first, but nonetheless can be “solved” using standard mathematical techniques. Conway first described the sequence in “The Weird and Wonderful Chemistry of Audioactive Decay”, Eureka 46:5–18, 1986 — there might be an application or two mentioned there.
@Nathaniel
Hi, I’ve also previously been thinking about the roman number look and say sequence, especially after I saw this post for the first time.
From what I can see, a major initial problem is that RNLAS doesn’t have atom boundaries in Conway’s sense – after a small number of iterations, only the letters I and V are interesting, and any string will have descendants starting with both I and V.
However I don’t think this is fatal – I think there still is a cosmological theorem, it just requires a relaxing of the requirements. In particular, I have found a 7-period of patterns that tends to occur frequently, and which grow so fast that information cannot cross them – which I think is enough to hope for setting up virtual elements with a matrix. |II|V|III|V|IIII| where | represents a block boundary is one of the seeds for that pattern period. (Note that the initial V’s produced by iterating the patterns are not to be considered part of them – in fact I found them by iterating RNLAS throwing away initial V’s at each step.)
To summarize, I think RNLAS evolves something as follows, but only the initial steps are proved (I hope this HTML list works, as I see no preview button):
All letters other than I and V shrink to single transuranics that behave essentially as V followed by an atom boundary (the only ones to occur). From this point I invented a shorter notation:
3_represents the two blocks IIIVV and4represents IIIIV.The beginning and end of the string settles down into a handful of possible growing patterns (the beginning ones only grow linearly, but still fast enough that disturbances cannot quite catch up with them.) . The interior temporarily settles into long strings of period 2 patterns in which
2_ 5 , 3 5 and 3_ 6alternate, and1 -> 2 -> 4disturbances which move leftward through the period 2 patterns, modifying them and causing growth (as a 4 is the only group size which causes a split.)After O(n) time enough disturbances will have passed through the strings that every original cell will have transformed into the 7-period pattern. At this time there will hopefully only be a finite number of possibilities for interacting regions – except for the detail that both the beginning of the string and the 7-period pattern has linearly growing tails of arbitrary length – but as these always grow faster than anything can catch up with them, I think this growth can be reanalyzed as part of the following pattern when setting up the matrix.
@Ørjan Johansen
Well that didn’t work entirely, my list got no bullets and I also forgot that < is dangerous: The period 2 patterns should be (knock on wood)
2_ <-> 5 , 3 <-> 5 and 3_ <-> 6.@Ørjan Johansen
Er,
3 <-> 5_;_(two V’s) alternate.I now have a calculated rate of growth for roman numeral look-and-say: The unique real root of the polynomial x^19 – x^8 – x^5 – x^2 – 1, or approximately 1.0980785015708145. (According to Wolfram Alpha the polynomial has an x^2 – x + 1 factor, so it’s really degree 17.)