Blog > A Derivation of Conway’s Degree-71 “Look-and-Say” Polynomial

A Derivation of Conway’s Degree-71 “Look-and-Say” Polynomial

October 31st, 2010

The look-and-say sequence is the sequence of numbers 1, 11, 21, 1211, 111221, 312211, …, in which each term is constructed by “reading” the previous term in the sequence. For example, the term 1 is read as “one 1″, which becomes the next term: 11. Then 11 is read as “two ones”, which becomes the next term: 21, and so on.

The remarkable thing about this sequence is that even though it seems at first glance to be quite arbitrary and non-mathematical, it has some interesting properties that were unearthed by John Conway. Most notably, he showed that the number of digits in each term of the sequence on average grows by about 30% from one term to the next. A bit more specifically, he showed that if Ln is the number of digits in the nth term in the sequence, then

where λ is the unique positive real root of the following degree-71 polynomial:

In order to demystify this seemingly bizarre fact, in this post we will show where this polynomial comes from and prove that the above limit does indeed equal its largest root (which happens to be its one and only positive real root).

The Cosmological Theorem

What lets us formally study the look-and-say sequence is a rather ominous-sounding result known as the cosmological theorem, which says that the eighth term and every term after it in the sequence is made up of one or more of 92 “basic” non-interacting subsequences. These 92 basic subsequences are summarized in lexicographical order in the following table. The fourth column in the table says what other subsequence(s) the given subsequence evolves into. For example, the first subsequence, 1112, evolves into the 63rd subsequence: 3112. Similarly, the second subsequence, 1112133, evolves into the 64th subsequence followed by the 62nd subsequence: 31121123.

# Subsequence Length Evolves Into
1 1112 4 (63)
2 1112133 7 (64)(62)
3 111213322112 12 (65)
4 111213322113 12 (66)
5 1113 4 (68)
6 11131 5 (69)
7 111311222112 12 (84)(55)
8 111312 6 (70)
9 11131221 8 (71)
10 1113122112 10 (76)
11 1113122113 10 (77)
12 11131221131112 14 (82)
13 111312211312 12 (78)
14 11131221131211 14 (79)
15 111312211312113211 18 (80)
16 111312211312113221133211322112211213322112 42 (81)(29)(91)
17 111312211312113221133211322112211213322113 42 (81)(29)(90)
18 11131221131211322113322112 26 (81)(30)
19 11131221133112 14 (75)(29)(92)
20 1113122113322113111221131221 28 (75)(32)
21 11131221222112 14 (72)
22 111312212221121123222112 24 (73)
23 111312212221121123222113 24 (74)
24 11132 5 (83)
25 1113222 7 (86)
26 1113222112 10 (87)
27 1113222113 10 (88)
28 11133112 8 (89)(92)
29 12 2 (1)
30 123222112 9 (3)
31 123222113 9 (4)
32 12322211331222113112211 23 (2)(61)(29)(85)
33 13 2 (5)
34 131112 6 (28)
35 13112221133211322112211213322112 32 (24)(33)(61)(29)(91)
36 13112221133211322112211213322113 32 (24)(33)(61)(29)(90)
37 13122112 8 (7)
38 132 3 (8)
39 13211 5 (9)
40 132112 6 (10)
41 1321122112 10 (21)
42 132112211213322112 18 (22)
43 132112211213322113 18 (23)
44 132113 6 (11)
45 1321131112 10 (19)
46 13211312 8 (12)
47 1321132 7 (13)
48 13211321 8 (14)
49 132113212221 12 (15)
50 13211321222113222112 20 (18)
51 1321132122211322212221121123222112 34 (16)
52 1321132122211322212221121123222113 34 (17)
53 13211322211312113211 20 (20)
54 1321133112 10 (6)(61)(29)(92)
55 1322112 7 (26)
56 1322113 7 (27)
57 13221133112 11 (25)(29)(92)
58 1322113312211 13 (25)(29)(67)
59 132211331222113112211 21 (25)(29)(85)
60 13221133122211332 17 (25)(29)(68)(61)(29)(89)
61 22 2 (61)
62 3 1 (33)
63 3112 4 (40)
64 3112112 7 (41)
65 31121123222112 14 (42)
66 31121123222113 14 (43)
67 3112221 7 (38)(39)
68 3113 4 (44)
69 311311 6 (48)
70 31131112 8 (54)
71 3113112211 10 (49)
72 3113112211322112 16 (50)
73 3113112211322112211213322112 28 (51)
74 3113112211322112211213322113 28 (52)
75 311311222 9 (47)(38)
76 311311222112 12 (47)(55)
77 311311222113 12 (47)(56)
78 3113112221131112 16 (47)(57)
79 311311222113111221 18 (47)(58)
80 311311222113111221131221 24 (47)(59)
81 31131122211311122113222 23 (47)(60)
82 3113112221133112 16 (47)(33)(61)(29)(92)
83 311312 6 (45)
84 31132 5 (46)
85 311322113212221 15 (53)
86 311332 6 (38)(29)(89)
87 3113322112 10 (38)(30)
88 3113322113 10 (38)(31)
89 312 3 (34)
90 312211322212221121123222113 27 (36)
91 312211322212221121123222112 27 (35)
92 32112 5 (37)

The important thing about this particular basis of subsequences is that the evolution of any sequence made up of these subsequences is determined entirely by the evolution rule for the subsequences given in the final column of the above table. For example, the eighth term in the look-and-say sequence is 1113213211 = (24)(39). The subsequence (24) evolves into (83) and the subsequence (39) evolves into (9), so the ninth term in the look-and-say sequence is (83)(9), which is 31131211131221.

Computing the Number of Digits in Sequences

Since the evolution of every term in the look-and-say sequence after the eighth can be computed using the table above, we can easily compute the length of every term after the eighth as well. For example, the eighth term in the sequence evolves into (83)(9), so the number of digits of the ninth term in the sequence is 6 + 8 = 14. The subsequence (83) evolves into a subsequence with 10 digits, and (9) evolves into a subsequence with 10 digits, so the tenth term in the look-and-say sequence has 10 + 10 = 20 digits.

All of the information about how the lengths of the 92 subsequences change can be represented in a 92×92 matrix T. In particular, the matrix T has its (i,j) entry equal to Cij × ℓi/ℓj, where Cij is the number of times subsequence (i) appears in the evolution rule for subsequence (j) and ℓi is the length of subsequence (i). This matrix is represented in the following image – white squares represent zero entries in the matrix, and black squares represent the number 2, which is the largest value present in the matrix. Shades of grey represent non-zero numbers, with larger numbers being darker.

Then if we represent a term in the look-and-say sequence as a vector v with its ith entry being ci × ℓi, where ci is the number of times the subsequence (i) appears in that term, we find that the sum of the entries in v is the total length of that term of the look-and-say sequence. More important, however, is the fact that the sum of the entries in Tv is the length of the next term in the look-and-say sequence. The sum of the entries in T2v is the length of the next term in the look-and-say sequence, and so on. So we have found a degree-92 recurrence relation for the length of terms in the look-and-say sequence, and the corresponding transition matrix is T.

Computing the Limit

It is a basic fact of linear homogeneous recurrence relations that a closed-form solution to the recurrence relation can be written down in terms of the eigenvalues of the transition matrix (see the linked Wikipedia page for specifics). As a corollary of this, the limiting ratio of terms in the sequence is equal to the spectral radius of the transition matrix. Fortunately, the transition matrix in this case is quite sparse, so its characteristic polynomial isn’t too difficult to compute:

Indeed, the degree-71 polynomial that λ is a root of is one of the factors of the characteristic polynomial of the transition matrix T. All that remains to do is to get MATLAB to compute the largest root of that polynomial (i.e., the spectral radius of T):

>> max(abs(eig(T)))

ans =
    1.303577269034287

The matrix T is attached below for those who would like to play with it. Something fun to think about: what do the rational eigenvalues (-1, 0, and 1) of T represent?

Download: Transition matrix [plaintext file]

Update [March 17, 2013]: Entry 91 of the subsequence table has been corrected – thanks to Marcus Stuhr and liuguangxi for the correction.

  1. November 1st, 2010 at 21:05 | #1

    That polynomial is a thing of beauty! I have often seen the sequence, 1, 11, 21, 1211, 111221, 312211, used as a fun math puzzle, but I have never seen it examined with such depth. I also did not know that it was called “look-and-say” sequence. Is the Conway mentioned in your title John Horton Conway of Conway’s Game of Life fame?

  2. November 1st, 2010 at 22:23 | #2

    @WebsterLin – That is indeed the same Conway. Quite a guy :)

  3. andy
    July 4th, 2011 at 00:43 | #3

    I guess the max root 1.3035… is an irrational number? (afaik MATLAB cuts off the number after the 15th decimal by default, thus suggesting the number to be rational)

  4. July 4th, 2011 at 01:13 | #4

    @andy – Yes, it’s irrational. The rational root theorem says that the only possible rational roots of that degree-71 polynomial are ±1, ±2, ±3, and ±6. Plugging those values into the polynomial reveals that none of them actually are roots, so it has no rational roots.

  5. epiclolz
    March 16th, 2013 at 21:08 | #5

    to anyone who may want to use this page for any reason… there is exactly one error in the big table

  6. Marcus Stuhr
    March 16th, 2013 at 22:19 | #6

    Entry 91 is incorrect

  7. liuguangxi
    March 17th, 2013 at 00:48 | #7

    Entry 91 should be 312211322212221121123222112

  8. Anders
    March 17th, 2013 at 09:17 | #8

    What reason would that be? :D

    Thanks for the blog post and thanks for the correction!

  9. Mike
    March 19th, 2013 at 07:52 | #9

    Correction to 91 has messed up the ordering. If (and only if!) you wish to restore the lexical ordering, the atoms at entries 90 & 91 should be swapped. Their descendants are respectively 35 and 36, and the descendants of 16 17 35 and 36 would also then need amending to respectively: 80 28 89, 80 28 90, 23 32 60 28 89, 23 32 60 28 90 (omitting the brackets). I’d been using the Conway ordering, so it’s worth checking whether I’ve amended my indexes correctly.

  10. jpatou
    March 20th, 2013 at 05:10 | #10

    I tried to compute this in Python starting from the 8th term and using a transition matrix at power n-8. My results arre correct until the 27th term and the 28th is false. What do you think can be wrong ?

  11. jpatou
    March 20th, 2013 at 09:37 | #11

    Sorry for that. I just corrected my mistake. I was thinking that there were only 1 in the transition matrix. I missed that (29) appears twice in the evolution of (60).

  12. Amic
    March 21st, 2013 at 22:17 | #12

    Here is a thought the signification of the rational eigenvalues.

    Taking a vector of α(90)-α(91)+β(35)-β(36), thinking of it as a real quantities of elements 90,91,35 and 36, it becomes after applying the sequence α(36)-α(35)+β(91)-β(90). So with β=α, we get an eigenvector for the value -1.

    Of course (61) is an eigenvector for the value 1…

    It requires more work to get an eigenvector for the value 0, or to get the dimension of the eigenspaces.

  13. Amic
    March 21st, 2013 at 22:23 | #13

    It also works with β=-α to get an eigenvector for the eigenvalue 1…

  14. Anders
    March 23rd, 2013 at 03:16 | #14

    Empirically it is clear that the growth rate tends to the spectral radius, but how can this be rigorously proven?

    Equivalently, how can it be shown that the vector corresponding to the eighth element has a component in the direction of the largest eigenvalue in the Jordan basis? (Remember, it’s not orthogonal in general.)

  15. Andrew
    May 29th, 2013 at 05:18 | #15

    How were the elements derived? It seems like a rather difficult task..

  16. May 29th, 2013 at 20:58 | #16

    @Andrew – Computer search carried out by Conway. The original code that carried out the search is long gone, but Ekhad and Zeilberger independently re-did the search much later, and their code is available here.

  17. July 28th, 2014 at 04:04 | #17

    You ought to be able to run the business sans
    worrying too much about its financial aspect.
    They will allow you to upload and download accounts from anywhere.
    Understand that when you enter a major tax franchise or chain your taxes are most likely being
    prepared by a trained.

  1. November 2nd, 2010 at 02:16 | #1
  2. March 28th, 2011 at 09:40 | #2
  3. June 8th, 2011 at 02:03 | #3
  4. August 18th, 2013 at 12:25 | #4