In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the look-and-say sequence is the
sequence of integers beginning as follows:
: 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, ... .
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 1s" or 21.
* 21 is read off as "one 2, one 1" or 1211.
* 1211 is read off as "one 1, one 2, two 1s" or 111221.
* 111221 is read off as "three 1s, two 2s, one 1" or 312211.
The look-and-say sequence was analyzed by
John Conway[
Reprinted as
]
after he was introduced to it by one of his students at a party.
The idea of the look-and-say sequence is similar to that of
run-length encoding
Run-length encoding (RLE) is a form of lossless data compression in which ''runs'' of data (sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original ...
.
If started with any digit ''d'' from 0 to 9 then ''d'' will remain indefinitely as the last digit of the sequence. For any ''d'' other than 1, the sequence starts as follows:
: ''d'', 1''d'', 111''d'', 311''d'', 13211''d'', 111312211''d'', 31131122211''d'', …
Ilan Vardi has called this sequence, starting with ''d'' = 3, the Conway sequence . (for ''d'' = 2, see )
Basic properties
Growth
The sequence grows indefinitely. In fact, any variant defined by starting with a different integer seed number will (eventually) also grow indefinitely, except for the
degenerate
Degeneracy, degenerate, or degeneration may refer to:
Arts and entertainment
* Degenerate (album), ''Degenerate'' (album), a 2010 album by the British band Trigger the Bloodshed
* Degenerate art, a term adopted in the 1920s by the Nazi Party i ...
sequence: 22, 22, 22, 22, ...
Digits presence limitation
No digits other than 1, 2, and 3 appear in the sequence, unless the seed number contains such a digit or a run of more than three of the same digit.
[
]
Cosmological decay
Conway's cosmological theorem asserts that every sequence eventually splits ("decays") into a sequence of "atomic elements", which are finite subsequences that never again interact with their neighbors. There are 92 elements containing the digits 1, 2, and 3 only, which John Conway named after the 92 naturally-occurring
chemical element
A chemical element is a species of atoms that have a given number of protons in their atomic nucleus, nuclei, including the pure Chemical substance, substance consisting only of that species. Unlike chemical compounds, chemical elements canno ...
s up to uranium, calling the sequence audioactive. There are also two "
transuranic" elements (Np and Pu) for each digit other than 1, 2, and 3.
Below is a table of all such elements:
Growth in length
The terms eventually grow in length by about 30% per generation. In particular, if ''L''
''n'' denotes the number of digits of the ''n''-th member of the sequence, then the
limit
Limit or Limits may refer to:
Arts and media
* ''Limit'' (manga), a manga by Keiko Suenobu
* ''Limit'' (film), a South Korean film
* Limit (music), a way to characterize harmony
* "Limit" (song), a 2016 single by Luna Sea
* "Limits", a 2019 ...
of the ratio
exists and is given by
::
where λ = 1.303577269034... is an
algebraic number
An algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio, (1 + \sqrt)/2, is an algebraic number, because it is a root of th ...
of degree 71.
This fact was proven by Conway, and the constant λ is known as Conway's
constant. The same result also holds for every variant of the sequence starting with any seed other than 22.
Conway's constant as a polynomial root
Conway's constant is the unique positive
real root of the following
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
:
:
This polynomial was correctly given in Conway's original ''Eureka'' article,
but in the reprinted version in the book edited by Cover and Gopinath
the term
was incorrectly printed with a minus sign in front.
Popularization
The look-and-say sequence is also popularly known as the Morris Number Sequence, after cryptographer
Robert Morris, and the puzzle "What is the next number in the sequence 1, 11, 21, 1211, 111221?" is sometimes referred to as the Cuckoo's Egg, from a description of Morris in
Clifford Stoll
Clifford Paul "Cliff" Stoll (born June 4, 1950) is an American astronomer, author and teacher.
He is best known for his investigation in 1986, while working as a systems administrator at the Lawrence Berkeley National Laboratory, that led to th ...
's book ''
The Cuckoo's Egg''.
FAQ about Morris Number Sequence
/ref>
Variations
There are many possible variations on the rule used to generate the look-and-say sequence. For example, to form the "pea pattern" one reads the previous term and counts all instances of each digit, listed in order of their first appearance, not just those occurring in a consecutive block. So beginning with the seed 1, the pea pattern proceeds 1, 11 ("one 1"), 21 ("two 1s"), 1211 ("one 2 and one 1"), 3112 ("three 1s and one 2"), 132112 ("one 3, two 1s and one 2"), 311322 ("three 1s, one 3 and two 2s"), etc. This version of the pea pattern eventually forms a cycle with the two "atomic" terms 23322114 and 32232114.
Other versions of the pea pattern are also possible; for example, instead of reading the digits as they first appear, one could read them in ascending order instead. In this case, the term following 21 would be 1112 ("one 1, one 2") and the term following 3112 would be 211213 ("two 1s, one 2 and one 3").
These sequences differ in several notable ways from the look-and-say sequence. Notably, unlike the Conway sequences, a given term of the pea pattern does not uniquely define the preceding term. Moreover, for any seed the pea pattern produces terms of bounded length: This bound will not typically exceed (22 digits for decimal
The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral ...
: ) and may only exceed (30 digits for decimal radix) in length for long, degenerate, initial seeds (sequence of "100 ones", etc.). For these extreme cases, individual elements of decimal sequences immediately settle into a permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or pro ...
of the form where here the letters are placeholders for digit counts from the preceding sequence element.
Since the sequence is infinite, and the length of each element is bounded, it ''must'' eventually repeat, due to the pigeonhole principle
In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, if one has three gloves (and none is ambidextrous/reversible), then there mu ...
. As a consequence, pea pattern sequences are always eventually periodic.
See also
* Gijswijt's sequence
* Kolakoski sequence
In mathematics, the Kolakoski sequence, sometimes also known as the Oldenburger–Kolakoski sequence, is an infinite sequence of symbols that is the sequence of run lengths in its own run-length encoding. It is named after the recreational mathe ...
* Autogram
An autogram ( grc, αὐτός = self, = letter) is a sentence that describes itself in the sense of providing an inventory of its own characters. They were invented by Lee Sallows, who also coined the word ''autogram''. An essential feature is th ...
Notes
References
External links
Conway speaking about this sequence
and telling that it took him some explanations to understand the sequence.
Implementations in many programming languages
on Rosetta Code
Rosetta Code is a wiki-based programming website with implementations of common algorithms and solutions to various programming problems in many different programming languages. It is named for the Rosetta Stone, which has the same text inscri ...
*
Look and Say sequence generator
p
*
A Derivation of Conway’s Degree-71 “Look-and-Say” Polynomial
{{Algebraic numbers
Base-dependent integer sequences
Algebraic numbers
Mathematical constants
John Horton Conway