Jump to content

Look-and-say sequence

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Andersyu31415 (talk | contribs) at 14:57, 23 August 2022 (→Cosmological decay: Included a table of all the "atomic elements"). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
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][3]

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

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)[5]

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

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

where λ = 1.303577269034... (sequence A014715 in the OEIS) is an algebraic number of degree 71.[5] 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):

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 was incorrectly printed with a minus sign in front.[7]

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.[8][9]

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

References

  1. ^ a b c d Conway, J. H. (January 1986). "The Weird and Wonderful Chemistry of Audioactive Decay" (PDF). Eureka. 46: 5–16. Reprinted as Conway, J. H. (1987). "The Weird and Wonderful Chemistry of Audioactive Decay". In Cover, Thomas M.; Gopinath, B. (eds.). 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. ^ Look-and-Say Numbers (feat John Conway) - Numberphile on YouTube
  4. ^ Conway Sequence, MathWorld, accessed on line February 4, 2011.
  5. ^ a b c d Martin, Oscar (2006). "Look-and-Say Biochemistry: Exponential RNA and Multistranded DNA" (PDF). American Mathematical Monthly. 113 (4). Mathematical association of America: 289–307. doi:10.2307/27641915. ISSN 0002-9890. JSTOR 27641915. Archived from the original (PDF) on 2006-12-24. Retrieved January 6, 2010.
  6. ^ 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.
  7. ^ Vardi, Ilan (1991). Computational Recreations in Mathematica. Addison-Wesley. ISBN 0-201-52989-0.
  8. ^ Robert Morris Sequence
  9. ^ FAQ about Morris Number Sequence
Retrieved from "https://en.wikipedia.org/w/index.php?title=Look-and-say_sequence&oldid=1106184389"