Last week I introduced an integer sequence that begins: 1, 11, 21, 1211, 111221, … This sequence is called the “look and say” sequence. It is also known as the Robert Morris sequence. It was discovered and described in 1986 by John Conway. It was popularized (somewhat) by Clifford Stoll in his 1990 book The Cuckoo’s Egg, an account of the pursuit of a computer hacker who broke into a Lawrence Berkeley National Laboratory computer.
I read it first in Stoll’s The Cuckoo’s Eggbut couldn’t solve it. Stoll himself was kind enough to reply to my e-mail, circa 1991, with the solution, which is as follows. The first term of the sequence, 1, is arbitrary. To generate any subsequent term, read the digits of the previous one in the following way (taken from Wikipedia):
- 1 is read off as “one 1” or 11.
- 11 is read off as “two 1’s” or 21.
- 21 is read off as “one 2, then one 1” or 1211.
- 1211 is read off as “one 1, then one 2, then two 1’s” or 111221.
Therefore, the next term is generated by reading 111221 as “three 1, then two 2, then one 1” or 312211. You can probably continue the sequence from there yourself.
The look and say sequence has the following properties:
- Starting with the value 22, the sequence repeats itself (22, 22, 22, …) indefinitely.
- Starting with any value other than 22, the length of sequence terms eventually grows larger than any finite number.
- Starting with the value 1 (among others), only the digits 1, 2, and 3 appear in any subsequent term.
Some might notice that the sequence is related to run-length coding variants of data compression. The sequence has other mathematical properties beyond the scope of this post. To learn more about them, see the entry in the The On-Line Encyclopedia of Integer Sequences or Wolfram MathWorld.
Finally, what I like most about the sequence is that it uses numbers in two ways: as representations of cardinality and as nominal numbers. That is, consider the look and say sequence beginning 1, 11, 21, … The second term of the sequence 11 describes the first term 1 using the number “1” first to denote cardinality (the number of elements) and then the number “1” as the arbitrary notation to identify the particular number.
To make this distinction explicit, consider the sequence beginning with the number d. The sequence would then be: d, 1d, … Here the “1” in the second term is a cardinal number. It counts the number of ds in the first term. Then the “d” in the second term just names the number that is counted.
