The Look-and-Say sequence is a sequence of numbers starting as follows:
1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ... (sequence A005150 in OEIS ).
Each subsequent number is generated from the previous one by concatenating a digit, which consists of a group of identical digits and the number of digits in this group, for each group of identical digits in a number. For example:
- 1 reads as “one unit,” that is, 11
- 11 reads as “two units,” that is, 21
- 21 reads as “one deuce, one unit”, that is 1211
- 1211 reads as “one unit, one two, two units”, that is, 111221
- 111221 reads as “three units, two deuces, one unit”, that is, 312211
- 312211 reads as “one three, one unit, two deuces, two units”, that is 13112221
The look-and-say sequence was proposed by John Conway [1] .
For an arbitrary digit d , except for unity, as the initial, the sequence takes the form:
d , 1 d , 111 d , 311 d , 13211 d , 111312211 d , 31131122211 d , ...
Content
Key Features
Growth
The sequence grows endlessly. In fact, any variant of the sequence with an integer initial number will grow indefinitely. The exception is the sequence:
22, 22, 22, 22, 22, ... (sequence A010861 in OEIS ).
Limit the numbers used
No digits except 1, 2 and 3 are found in the sequence if the initial number does not contain other digits or a group of more than three digits [2] .
Number Length Increase
On average, numbers grow by 30% per iteration. If a denotes the length of the nth term of the sequence, then there is a limit to the ratio :
.
Here λ = 1.303577269034 ... is the Conway constant [2] . The same result holds for any variation of the sequence with an initial number other than 22.
Polynomial Returning Conway's Constant
Conway constant is the only positive material root of the polynomial:
In his original article, Conway makes a mistake by writing “-” instead of “+” before . But the value of λ given in his article is true [3] .
Popularization
The Look-and-Say sequence is also known as the Morris number sequence in honor of cryptographer . It is sometimes referred to as the “cuckoo egg” because of the puzzle “What is the next number in the sequence 1, 11, 21, 1211, 111221?” Described by Morris in Clifford Stoll’s book “The Cuckoo Egg”.
Variations
There are many variations of the rules for creating sequences like Look-and-Say. For example, the sequence “pea pattern”. It differs from Look-and-Say in that in order to get a new number in it you need to count all the same numbers in a number. Starting from the number 1, we get: 1, 11 (one unit), 21 (two units), 1211 (one two, one unit), 3112 (three units, one two), 132112 (one three, two units, one two) , 312213 (three units, two deuces, one three), etc. As a result, the sequence comes to a cycle of two numbers, 23322114 and 32232114. [4]
There is another option that differs from the pea pattern in that the numbers are counted in ascending order, and not as they appear. Starting from one, we get the sequence: 1, 11, 21, 1112, 3112, 211213, 312213, ...
These sequences have notable differences from Look-and-Say. Unlike the Conway sequence, this member in the pea pattern does not uniquely identify the previous member. The length of the numbers in the “pea pattern” is limited and, for the b-number system , does not exceed 2b, and reaches 3b for large initial numbers (for example, “one hundred units”).
Given that this sequence is infinite and its length is limited, it must ultimately be repeated according to the Dirichlet principle . As a result, these sequences are always periodic.
See also
- Spikelet sequence
- Guiswith sequence
Notes
- ↑ John Horton Conway. The Weird and Wonderful Chemistry of Audioactive Decay (English) // Eureka. - 1986 .-- January ( vol. 46 ). - P. 5-16 . Archived on October 11, 2014.
- ↑ 1 2 Oscar Martin. Look-and-Say Biochemistry: Exponential RNA and Multistranded DNA (English) // American Mathematical Monthly. - 2006. - Vol. 113 , no. 4 . - P. 289-307 . - ISSN 0002-9890 . Archived December 24, 2006.
- ↑ Ilan Vardi. Computational Recreation in Mathematica.
- ↑ Ascending Pea Pattern generator .