Перегляд вихідного коду сторінки Послідовність «подивися-і-скажи»

[[Файл:Conway's constant.svg|мини|300x300пкс|Графіки показують зростання кількості цифр у послідовності «подивися-і-скажи» з початковими числами: 1 (синій), 13 (фіолетовий), 23 (червоний) та 312 (зелений). Ці графіки прямують до прямих ліній (вертикальна вісь має [[Логарифмічна шкала|логарифмічний масштаб]])]]

'''Послідовність «подивися-і-скажи»'''&nbsp;— це послідовність чисел, що починається так:

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, … (послідовність [[oeis:A005150|A005150]] в [[Інтерактивна енциклопедія цілочислових послідовностей|OEIS]]).

Кожне наступне число будується за попереднім [[Конкатенація|послідовним записом]] для кожної групи однакових цифр кількості цифр у цій групі та самої цифри, з якої складається група. Наприклад:

* 1 читається як «одна одиниця», тобто 11
* 11 читається як «дві одиниці», тобто 21
* 21 читається як «одна двійка, одна одиниця», тобто 1211
* 1211 читається як «одна одиниця, одна двійка, дві одиниці», тобто 111221
* 111221 читається як «три одиниці, дві двійки, одна одиниця», тобто 312211
* 312211 читається як «одна трійка, одна одиниця, дві двійки, дві одиниці», тобто 13112221

Послідовність «подивися-і-скажи» запропонував [[Джон Конвей]].<ref name="Conway-original-article">
{{cite journal |last=Conway |first=J. H. |author-link=Джон Конвей |date=January 1986 |title=The Weird and Wonderful Chemistry of Audioactive Decay |url=https://www.archim.org.uk/eureka/archive/Eureka-46.pdf |journal=Eureka |volume=46 |pages=5–16}}
Reprinted as
{{cite book |title=Open Problems in Communication and Computation |last=Conway |first=J. H. |date=1987 |editor-last=Cover |editor-first=Thomas M. |publisher=[[Springer-Verlag]] |pages=173–188 |chapter=The Weird and Wonderful Chemistry of Audioactive Decay |isbn=0-387-96621-8 |author-link=Джон Конвей |editor-last2=Gopinath |editor-first2=B.}}
</ref>

Для довільної початкової цифри ''d'', крім одиниці, послідовність набуває вигляду:

''d'', 1''d'', 111''d'', 311''d'', 13211''d'', 111312211''d'', 31131122211''d'', …

== Основні властивості ==

[[Файл:Conway constant.png|мини|350x350пкс|Коріння багаточлена Конвея на комплексній площині]]

=== Зростання ===
Послідовність зростає нескінченно. Фактично, будь-який варіант послідовності з цілим початковим числом зростатиме нескінченно. Виняток становить послідовність:

22, 22, 22, 22, 22, … (послідовність [[oeis:A010861|A010861]] в [[Інтерактивна енциклопедія цілочислових послідовностей|OEIS]]).

=== Обмеження цифр, що використовуються ===
Жодні цифри, крім 1, 2 і 3 не зустрічаються в послідовності, якщо початкове число не містить інших цифр або групи з більш ніж трьох цифр<ref name=":2">{{Стаття|author=Oscar Martin.|title=Look-and-Say Biochemistry: Exponential RNA and Multistranded DNA|url=http://www.uam.es/personal_pdi/ciencias/omartin/Biochem.PDF|language=en|видання=American Mathematical Monthly|тип=|date=2006|місяць=|число=|том=113|номер=4|pages=289—307|issn=0002-9890|archiveurl=https://web.archive.org/web/20061224154744/http://www.uam.es/personal_pdi/ciencias/omartin/Biochem.PDF|archivedate=2006-12-24}}</ref>.

=== Зростання довжини чисел ===
У середньому числа виростають на 30&nbsp;% за ітерацію. Якщо <math>L_n</math> позначає довжину n-го члена послідовності, то існує границя відношення <math>\frac {L_{n+1}} {L_n}</math> :

<math>\lim_{n \to \infty} \frac {L_{n+1}} {L_n} = \lambda</math>.

Тут λ = 1.303577269034 …&nbsp;— стала Конвея<ref name=":22">{{Стаття|author=Oscar Martin.|title=Look-and-Say Biochemistry: Exponential RNA and Multistranded DNA|url=http://www.uam.es/personal_pdi/ciencias/omartin/Biochem.PDF|language=en|видання=American Mathematical Monthly|тип=|date=2006|місяць=|число=|том=113|номер=4|pages=289—307|issn=0002-9890|archiveurl=https://web.archive.org/web/20061224154744/http://www.uam.es/personal_pdi/ciencias/omartin/Biochem.PDF|archivedate=2006-12-24}}</ref>. Цей результат справедливий для будь-якого варіанту послідовності з початковим числом, відмінним від 22.

=== Многочлен, який повертає сталу Конвея ===
Стала Конвея&nbsp;— це єдиний додатний дійсний корінь многочлена:

<math>\begin{align}
&\,\,\,\,\,\,\, x^{71} && &&- x^{69} &&- 2x^{68} &&- x^{67} &&+ 2x^{66}  &&+ 2x^{65} &&+ x^{64} &&- x^{63} \\
&- x^{62} &&- x^{61} &&- x^{60} &&- x^{59}  &&+ 2x^{58} &&+ 5x^{57} &&+ 3x^{56} &&- 2x^{55} &&- 10x^{54} \\
&- 3x^{53} &&- 2x^{52} &&+ 6x^{51} &&+ 6x^{50} &&+ x^{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} &&+ x^{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 &&- 6
\end{align}</math>



У своїй оригінальній статті Конвей помилково написав «−» замість «+» перед <math>x^{35}</math>. Але значення λ, наведене в його статті, правильне<ref>{{Книга
|автор = Ilan Vardi
|заголовок = Computational Recreation in Mathematica
|відповідальний = 
|видання = 
|місце = 
|видавництво = 
|рік = 
|сторінки = 
|сторінок = 
|ISBN = 
|isbn2 = 
}}</ref>.

== Популяризація ==
Послідовність «подивися-і-скажи» також відома як послідовність чисел Морріса на честь криптографа {{Не перекладено|Роберт Морріс (криптограф)|Роберта Морріса|en|Robert Morris (cryptographer)}}. Іноді її називають «зозулине яйце» через головоломку «Яке наступне число в послідовності 1, 11, 21, 1211, 111221?», за описом Морріса в книзі {{Нп|Кліффорд Столл|Кліффорда Столла|en|Clifford Stoll}} {{Нп|Зозулине яйце (книга)|«Зозулине яйце»|en|The Cuckoo's Egg (book)}}.

== Варіації ==
Існує багато варіантів правил для створення послідовностей, подібних до «подивися-і-скажи». Наприклад, послідовність «pea pattern». Вона відрізняється від «подивися-і-скажи» тим, що для отримання нового числа в ній потрібно підраховувати всі однакові цифри в числі. Починаючи з числа 1, отримаємо: 1, 11 (одна одиниця), 21 (дві одиниці), 1211 (одна двійка, одна одиниця), 3112 (три одиниці, одна двійка), 132112 (одна трійка, дві одиниці, одна двійка), 312213 (три одиниці, дві двійки, одна трійка) і&nbsp;т.&nbsp;д. Зрештою послідовність приходить до циклу з двох чисел, 23322114 і 32232114.<ref>{{Cite web|url=http://codegolf.stackexchange.com/questions/4642/ascending-pea-pattern-generator|title=Ascending Pea Pattern generator|last=|date=|website=|publisher=|archive-url=https://web.archive.org/web/20161017073638/http://codegolf.stackexchange.com/questions/4642/ascending-pea-pattern-generator|archive-date=2016-10-17|dead-url=no|access-date=2018-08-09}}</ref>

Існує інший варіант, який відрізняється від «pea pattern» тим, що цифри підраховуються в порядку зростання, а не в міру появи. Починаючи з одиниці, отримаємо послідовність: 1, 11, 21, 1112, 3112, 211213, 312213, …

Ці послідовності мають цікаві відмінності від «подивися-і-скажи». На відміну від послідовності Конвея, кожен член у «pea pattern» не однозначно визначає попередній член. Довжина чисел у «pea pattern» обмежена і, для [[Позиційна система числення|b-кової системи числення]], не перевищує 2b, і досягає 3b для великих початкових чисел (наприклад, «сто одиниць»).

Оскільки ця послідовність нескінченна і довжина її члена обмежена, вона, за [[Принцип Діріхле|принципом Диріхле]], повинна зрештою повторитися. Як наслідок, ці послідовності завжди періодичні.

== Примітки ==
{{reflist}}