Послідовність «подивися-і-скажи» — це послідовність чисел, що починається так:
1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, … (послідовність A005150 в OEIS).
Кожне наступне число будується за попереднім послідовним записом для кожної групи однакових цифр кількості цифр у цій групі та самої цифри, з якої складається група. Наприклад:
1 читається як «одна одиниця», тобто 11 11 читається як «дві одиниці», тобто 21 21 читається як «одна двійка, одна одиниця», тобто 1211 1211 читається як «одна одиниця, одна двійка, дві одиниці», тобто 111221 111221 читається як «три одиниці, дві двійки, одна одиниця», тобто 312211 312211 читається як «одна трійка, одна одиниця, дві двійки, дві одиниці», тобто 13112221
Послідовність «подивися-і-скажи» запропонував Джон Конвей.Reprinted as
Для довільної початкової цифри d, крім одиниці, послідовність набуває вигляду:
d, 1d, 111d, 311d, 13211d, 111312211d, 31131122211d, …
Основні властивості
Зростання Послідовність зростає нескінченно. Фактично, будь-який варіант послідовності з цілим початковим числом зростатиме нескінченно. Виняток становить послідовність:
22, 22, 22, 22, 22, … (послідовність A010861 в OEIS).
Обмеження цифр, що використовуються Жодні цифри, крім 1, 2 і 3 не зустрічаються в послідовності, якщо початкове число не містить інших цифр або групи з більш ніж трьох цифр.
Зростання довжини чисел У середньому числа виростають на 30 % за ітерацію. Якщо позначає довжину n-го члена послідовності, то існує границя відношення :
.
Тут λ = 1.303577269034 … — стала Конвея. Цей результат справедливий для будь-якого варіанту послідовності з початковим числом, відмінним від 22.
Многочлен, який повертає сталу Конвея Стала Конвея — це єдиний додатний дійсний корінь многочлена:
У своїй оригінальній статті Конвей помилково написав «−» замість «+» перед . Але значення λ, наведене в його статті, правильне.
Популяризація Послідовність «подивися-і-скажи» також відома як послідовність чисел Морріса на честь криптографа . Іноді її називають «зозулине яйце» через головоломку «Яке наступне число в послідовності 1, 11, 21, 1211, 111221?», за описом Морріса в книзі .
Варіації Існує багато варіантів правил для створення послідовностей, подібних до «подивися-і-скажи». Наприклад, послідовність «pea pattern». Вона відрізняється від «подивися-і-скажи» тим, що для отримання нового числа в ній потрібно підраховувати всі однакові цифри в числі. Починаючи з числа 1, отримаємо: 1, 11 (одна одиниця), 21 (дві одиниці), 1211 (одна двійка, одна одиниця), 3112 (три одиниці, одна двійка), 132112 (одна трійка, дві одиниці, одна двійка), 312213 (три одиниці, дві двійки, одна трійка) і т. д. Зрештою послідовність приходить до циклу з двох чисел, 23322114 і 32232114.
Існує інший варіант, який відрізняється від «pea pattern» тим, що цифри підраховуються в порядку зростання, а не в міру появи. Починаючи з одиниці, отримаємо послідовність: 1, 11, 21, 1112, 3112, 211213, 312213, …
Ці послідовності мають цікаві відмінності від «подивися-і-скажи». На відміну від послідовності Конвея, кожен член у «pea pattern» не однозначно визначає попередній член. Довжина чисел у «pea pattern» обмежена і, для b-кової системи числення, не перевищує 2b, і досягає 3b для великих початкових чисел (наприклад, «сто одиниць»).
Оскільки ця послідовність нескінченна і довжина її члена обмежена, вона, за принципом Диріхле, повинна зрештою повторитися. Як наслідок, ці послідовності завжди періодичні.
Примітки