Look-and-say sequence

From HandWiki
Short description: Integer sequence
The lines show the growth of the numbers of digits in the look-and-say sequences with starting points 23 (red), 1 (blue), 13 (violet), 312 (green). These lines (when represented in a logarithmic vertical scale) tend to straight lines whose slopes coincide with Conway's constant.

In mathematics, the look-and-say sequence is the sequence of integers beginning as follows:

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, ... (sequence A005150 in the OEIS).

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[1] after he was introduced to it by one of his students at a party.[2]Cite error: Invalid <ref> tag; refs with no name must have content

The idea of the look-and-say sequence is similar to that of run-length encoding.

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, 1d, 111d, 311d, 13211d, 111312211d, 31131122211d, …

Ilan Vardi has called this sequence, starting with d = 3, the Conway sequence (sequence A006715 in the OEIS). (for d = 2, see OEIS: A006751)[3]

Basic properties

Roots of the Conway polynomial plotted in the complex plane. Conway's constant is marked with the Greek letter lambda (λ).

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 sequence: 22, 22, 22, 22, ... (sequence A010861 in the OEIS)[4]

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.[4]

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 elements 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.[4][5] Below is a table of all such elements:

All "atomic elements" (Where Ek is included within the derivate of Ek+1 except Np and Pu)[1]
Atomic number (n) Element name (Ek) Sequence Decays into[4] Abundance
1 H 22 H 91790.383216
2 He 13112221133211322112211213322112 Hf.Pa.H.Ca.Li 3237.2968588
3 Li 312211322212221121123222112 He 4220.0665982
4 Be 111312211312113221133211322112211213322112 Ge.Ca.Li 2263.8860325
5 B 1321132122211322212221121123222112 Be 2951.1503716
6 C 3113112211322112211213322112 B 3847.0525419
7 N 111312212221121123222112 C 5014.9302464
8 O 132112211213322112 N 6537.3490750
9 F 31121123222112 O 8521.9396539
10 Ne 111213322112 F 11109.006696
11 Na 123222112 Ne 14481.448773
12 Mg 3113322112 Pm.Na 18850.441228
13 Al 1113222112 Mg 24573.006696
14 Si 1322112 Al 32032.812960
15 P 311311222112 Ho.Si 14895.886658
16 S 1113122112 P 19417.939250
17 Cl 132112 S 25312.784218
18 Ar 3112 Cl 32997.170122
19 K 1112 Ar 43014.360913
20 Ca 12 K 56072.543129
21 Sc 3113112221133112 Ho.Pa.H.Ca.Co 9302.0974443
22 Ti 11131221131112 Sc 12126.002783
23 V 13211312 Ti 15807.181592
24 Cr 31132 V 20605.882611
25 Mn 111311222112 Cr.Si 26861.360180
26 Fe 13122112 Mn 35015.858546
27 Co 32112 Fe 45645.877256
28 Ni 11133112 Zn.Co 13871.123200
29 Cu 131112 Ni 18082.082203
30 Zn 312 Cu 23571.391336
31 Ga 13221133122211332 Eu.Ca.Ac.H.Ca.Zn 1447.8905642
32 Ge 31131122211311122113222 Ho.Ga 1887.4372276
33 As 11131221131211322113322112 Ge.Na 27.246216076
34 Se 13211321222113222112 As 35.517547944
35 Br 3113112211322112 Se 46.299868152
36 Kr 11131221222112 Br 60.355455682
37 Rb 1321122112 Kr 78.678000089
38 Sr 3112112 Rb 102.56285249
39 Y 1112133 Sr.U 133.69860315
40 Zr 12322211331222113112211 Y.H.Ca.Tc 174.28645997
41 Nb 1113122113322113111221131221 Er.Zr 227.19586752
42 Mo 13211322211312113211 Nb 296.16736852
43 Tc 311322113212221 Mo 386.07704943
44 Ru 132211331222113112211 Eu.Ca.Tc 328.99480576
45 Rh 311311222113111221131221 Ho.Ru 428.87015041
46 Pd 111312211312113211 Rh 559.06537946
47 Ag 132113212221 Pd 728.78492056
48 Cd 3113112211 Ag 950.02745646
49 In 11131221 Cd 1238.4341972
50 Sn 13211 In 1614.3946687
51 Sb 3112221 Pm.Sn 2104.4881933
52 Te 1322113312211 Eu.Ca.Sb 2743.3629718
53 I 311311222113111221 Ho.Te 3576.1856107
54 Xe 11131221131211 I 4661.8342720
55 Cs 13211321 Xe 6077.0611889
56 Ba 311311 Cs 7921.9188284
57 La 11131 Ba 10326.833312
58 Ce 1321133112 La.H.Ca.Co 13461.825166
59 Pr 31131112 Ce 17548.529287
60 Nd 111312 Pr 22875.863883
61 Pm 132 Nd 29820.456167
62 Sm 311332 Pm.Ca.Zn 15408.115182
63 Eu 1113222 Sm 20085.668709
64 Gd 13221133112 Eu.Ca.Co 21662.972821
65 Tb 3113112221131112 Ho.Gd 28239.358949
66 Dy 111312211312 Tb 36812.186418
67 Ho 1321132 Dy 47987.529438
68 Er 311311222 Ho.Pm 1098.5955997
69 Tm 11131221133112 Er.Ca.Co 1204.9083841
70 Yb 1321131112 Tm 1570.6911808
71 Lu 311312 Yb 2047.5173200
72 Hf 11132 Lu 2669.0970363
73 Ta 13112221133211322112211213322113 Hf.Pa.H.Ca.W 242.07736666
74 W 312211322212221121123222113 Ta 315.56655252
75 Re 111312211312113221133211322112211213322113 Ge.Ca.W 169.28801808
76 Os 1321132122211322212221121123222113 Re 220.68001229
77 Ir 3113112211322112211213322113 Os 287.67344775
78 Pt 111312212221121123222113 Ir 375.00456738
79 Au 132112211213322113 Pt 488.84742982
80 Hg 31121123222113 Au 637.25039755
81 Tl 111213322113 Hg 830.70513293
82 Pb 123222113 Tl 1082.8883285
83 Bi 3113322113 Pm.Pb 1411.6286100
84 Po 1113222113 Bi 1840.1669683
85 At 1322113 Po 2398.7998311
86 Rn 311311222113 Ho.At 3127.0209328
87 Fr 1113122113 Rn 4076.3134078
88 Ra 132113 Fr 5313.7894999
89 Ac 3113 Ra 6926.9352045
90 Th 1113 Ac 7581.9047125
91 Pa 13 Th 9883.5986392
92 U 3 Pa 102.56285249
Transuranic elements
93 Np 1311222113321132211221121332211n[note 1] Hf.Pa.H.Ca.Pu 0
94 Pu 31221132221222112112322211n[note 1] Np 0

Growth in length

The terms eventually grow in length by about 30% per generation. In particular, if Ln denotes the number of digits of the n-th member of the sequence, then the limit of the ratio [math]\displaystyle{ \frac{L_{n + 1}}{L_n} }[/math] exists and is given by [math]\displaystyle{ \lim_{n \to \infty} \frac{L_{n+1}}{L_{n}} = \lambda }[/math]

where λ = 1.303577269034... (sequence A014715 in the OEIS) is an algebraic number of degree 71.[4] 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 (sequence A137275 in the OEIS): [math]\displaystyle{ \begin{matrix} & &\qquad & &\qquad & &\qquad & & +1x^{71} & \\ -1x^{69} & -2x^{68} & -x^{67} & +2x^{66} & +2x^{65} & +1x^{64} & -1x^{63} & -1x^{62} & -1x^{61} & -1x^{60} \\ -1x^{59} & +2x^{58} & +5x^{57} & +3x^{56} & -2x^{55} & -10x^{54} & -3x^{53} & -2x^{52} & +6x^{51} & +6x^{50} \\ +1x^{49} & +9x^{48} & -3x^{47} & -7x^{46} & -8x^{45} & -8x^{44} & +10x^{43} & +6x^{42} & +8x^{41} & -5x^{40} \\ -12x^{39} & +7x^{38} & -7x^{37} & +7x^{36} & +x^{35} & -3x^{34} & +10x^{33} & +1x^{32} & -6x^{31} & -2x^{30} \\ -10x^{29} & -3x^{28} & +2x^{27} & +9x^{26} & -3x^{25} & +14x^{24} & -8x^{23} & & -7x^{21} & +9x^{20} \\ +3x^{19} & -4x^{18} & -10x^{17} & -7x^{16} & +12x^{15} & +7x^{14} & +2x^{13} & -12x^{12} & -4x^{11} & -2x^{10} \\ +5x^{9} & & +x^{7} & -7x^{6} & +7x^{5} & -4x^{4} & +12x^{3} & -6x^{2} & +3x^{1} & -6x^{0} \\ \end{matrix} }[/math]

This polynomial was correctly given in Conway's original Eureka article,[1] but in the reprinted version in the book edited by Cover and Gopinath[1] the term [math]\displaystyle{ x^{35} }[/math] was incorrectly printed with a minus sign in front.[6]

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's book The Cuckoo's Egg.[7][8]

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 2 × Radix + 2 digits (22 digits for decimal: radix = 10) and may only exceed 3 × Radix digits (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 of the form a0 b1 c2 d3 e4 f5 g6 h7 i8 j9 where here the letters a–j 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. As a consequence, pea pattern sequences are always eventually periodic.

See also

Notes

  1. ↑ 1.0 1.1 n can be any digit 4 or above.

References

  1. ↑ 1.0 1.1 1.2 1.3 Conway, J. H. (January 1986). "The Weird and Wonderful Chemistry of Audioactive Decay". Eureka 46: 5–16. https://www.archim.org.uk/eureka/archive/Eureka-46.pdf.  Reprinted as Conway, J. H. (1987). "The Weird and Wonderful Chemistry of Audioactive Decay". in Cover, Thomas M.. Open Problems in Communication and Computation. Springer-Verlag. pp. 173–188. ISBN 0-387-96621-8. 
  2. ↑ Roberts, Siobhan (2015). Genius at Play: The Curious Mind of John Horton Conway. Bloomsbury. ISBN 978-1-62040-593-2. 
  3. ↑ Conway Sequence, MathWorld, accessed on line February 4, 2011.
  4. ↑ 4.0 4.1 4.2 4.3 4.4 Martin, Oscar (2006). "Look-and-Say Biochemistry: Exponential RNA and Multistranded DNA". American Mathematical Monthly (Mathematical association of America) 113 (4): 289–307. doi:10.2307/27641915. ISSN 0002-9890. Archived from the original on 2006-12-24. https://web.archive.org/web/20061224154744/http://www.uam.es/personal_pdi/ciencias/omartin/Biochem.PDF. Retrieved January 6, 2010. 
  5. ↑ Ekhad, S. B., Zeilberger, D.: Proof of Conway's lost cosmological theorem, Electronic Research Announcements of the American Mathematical Society, August 21, 1997, Vol. 5, pp. 78–82. Retrieved July 4, 2011.
  6. ↑ Vardi, Ilan (1991). Computational Recreations in Mathematica. Addison-Wesley. ISBN 0-201-52989-0. 
  7. ↑ Robert Morris Sequence
  8. ↑ FAQ about Morris Number Sequence

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Look-and-say_sequence&oldid=3171228"