Look-and-say sequence
In mathematics, the look-and-say sequence is the sequence of integers beginning as follows:
- 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ...
To generate a member of the sequence from the previous member, read off the digits of the previous member, counting the number of digits in groups of the same digit. For example:
- 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.
- 111221 is read off as "three 1, then two 2, then one 1" or 312211.
The idea is similar to that of run-length encoding.
Basic properties
- The sequence grows indefinitely. In fact, any variant defined by starting with a different number will also grow indefinitely, except for the degenerate sequence 22, 22, 22, 22 ... .
- The 70th member of the sequence has 179,691,598 digits.
- No digits other than 1, 2, and 3 ever appear in the sequence, unless the seed number contains such a digit or a run of more than three of the same digit.
- Let be the length of the sequence on the th iteration. Then
- where is an algebraic number of degree 71 known as Conway's constant. This fact was proven by John Conway. This also holds for variants of the sequence starting with any integer other than 22.
Conway's constant is the unique positive solution of the following polynomial:
Origin
It was introduced and analyzed by John Conway in his 1986 paper "The Weird and Wonderful Chemistry of Audioactive Decay" (in Open Problems in Communication and Computation by Thomas M. Cover, B. Gopinath (Editor), Springer (December 1987) ISBN 0-387-96621-8).
Popularization
It is also popularly known as the Morris Number Sequence, after cryptographer Robert Morris, the puzzle is sometimes referred to as the Cuckoo's Egg from a description of Morris in Clifford Stoll's book The Cuckoo's Egg. [1], [2]