Последовательность «посмотри и скажи»
В математике последовательность « посмотри и скажи» — это последовательность целых чисел, начинающаяся следующим образом:
- 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, ... (последовательность A005150 в OEIS ).
Чтобы создать член последовательности из предыдущего члена, считайте цифры предыдущего члена, подсчитав количество цифр в группах одной и той же цифры. Например:
- 1 читается как «один 1» или 11.
- 11 читается как «две единицы» или 21.
- 21 читается как «один 2, один 1» или 1211.
- Число 1211 читается как «одна 1, одна 2, две единицы» или 111221.
- Число 111221 читается как «три единицы, две двойки, одна единица» или 312211.
Последовательность «посмотри и скажи» была проанализирована Джоном Конвеем. [1] после того, как его познакомил с этим один из его учеников на вечеринке. [2] [3]
Идея последовательности «посмотри и скажи» аналогична идее кодирования длин серий .
Если начать с любой цифры d от 0 до 9, то d останется на неопределенный срок последней цифрой последовательности. Для любого d, отличного от 1, последовательность начинается следующим образом:
- д , 1 д , 111 д , 311 д , 13211 д , 111312211 д , 31131122211 д , …
Илан Варди назвал эту последовательность, начиная с d = 3, последовательностью Конвея (последовательность A006715 в OEIS ). (для d = 2 см. OEIS : A006751 ) [4]
Основные свойства [ править ]
Рост [ править ]
Последовательность растет бесконечно. Фактически, любой вариант, определенный начиная с другого целочисленного начального номера, (в конечном итоге) также будет расти бесконечно, за исключением вырожденной последовательности: 22, 22, 22, 22, ... которая остается того же размера. (последовательность A010861 в ОЭИС ) [5]
Ограничение присутствия цифр [ править ]
В последовательности не появляются никакие цифры, кроме 1, 2 и 3, за исключением случаев, когда начальный номер содержит такую цифру или серию из более чем трех одинаковых цифр. [5]
распад Космологический
Конвея Космологическая теорема утверждает, что каждая последовательность в конечном итоге распадается («распадается») на последовательность «атомных элементов», которые представляют собой конечные подпоследовательности, которые никогда больше не взаимодействуют со своими соседями. Существует 92 элемента, содержащих только цифры 1, 2 и 3, которые Джон Конвей назвал в честь 92 встречающихся в природе химических элементов вплоть до урана , назвав последовательность аудиоактивной . Есть также два « трансурановых » элемента (Np и Pu) для каждой цифры, кроме 1, 2 и 3. [5] [6] Ниже представлена таблица всех таких элементов:
| Все «атомные элементы» (где E k включен в производную от E k+1, за исключением Np и Pu) [1] |
|---|
Рост в длину [ править ]
Сроки в конечном итоге увеличиваются в длине примерно на 30% за поколение. В частности, если L n обозначает количество цифр n -го члена последовательности, то предел отношения существует и задается
где λ = 1,303577269034... (последовательность A014715 в OEIS ) — алгебраическое число степени 71. [5] Этот факт был доказан Конвеем, а константа λ известна как Конвея константа . Тот же результат справедлив для каждого варианта последовательности, начинающегося с любого начального числа, отличного от 22.
Константа Конвея как корень полинома [ править ]
Константа Конвея — это уникальный положительный действительный корень следующего полинома (последовательность A137275 в OEIS ):
Этот полином был правильно указан в оригинальной Конвея «Эврика» : статье [1] но в переизданной версии в книге под редакцией Кавера и Гопинатха [1] термин было неправильно напечатано со знаком минус впереди. [7]
Популяризация [ править ]
Последовательность «посмотри и скажи» также широко известна как числовая последовательность Морриса в честь криптографа Роберта Морриса и головоломки «Какое следующее число в последовательности 1, 11, 21, 1211, 111221?» иногда упоминается как « Яйцо кукушки » из описания Морриса в Клиффорда Столла книге «Яйцо кукушки» . [8] [9]
Вариации [ править ]
 |
Существует множество возможных вариаций правила, используемого для создания последовательности «посмотри и скажи». Например, чтобы сформировать «шаблон горошины», нужно прочитать предыдущий термин и подсчитать все экземпляры каждой цифры, перечисленные в порядке их первого появления, а не только те, которые встречаются в последовательном блоке. Таким образом, начиная с семени 1, узор горошины продолжается 1, 11 («одна 1»), 21 («две единицы»), 1211 («одна 2 и одна 1»), 3112 («три единицы и одна 2»). , 132112 («одна тройка, две единицы и одна 2»), 311322 («три единицы, одна тройка и две двойки») и т. д. Эта версия горошины в конечном итоге образует цикл с двумя «атомарными» терминами 23322114 и 32232114.
Возможны и другие варианты узора «горошек»; например, вместо того, чтобы читать цифры по мере их первого появления, можно читать их в порядке возрастания. В этом случае член после 21 будет 1112 («один 1, один 2»), а член после 3112 будет 211213 («две единицы, одна 2 и одна 3»).
Эти последовательности во многом отличаются от последовательности «посмотри и скажи». Примечательно, что в отличие от последовательностей Конвея, данный член шаблона гороха не определяет однозначно предыдущий термин. Более того, для любого семени шаблон горошины создает члены ограниченной длины: эта граница обычно не превышает 2 × цифр счисления + 2 цифры (22 цифры для десятичной системы счисления : основание = 10 ) и может превышать только 3 × системы счисления цифры (30 цифр для десятичной системы счисления). ) по длине для длинных вырожденных начальных семян (последовательность «100 единиц» и т. д.). В этих крайних случаях отдельные элементы десятичных последовательностей немедленно превращаются в перестановку вида a 0 b 1 c 2 d 3 e 4 f 5 g 6 h 7 i 8 j 9 , где здесь буквы a – j являются заполнителями для количества цифр. из предыдущего элемента последовательности.
Поскольку последовательность бесконечна, а длина каждого элемента ограничена, она должна в конечном итоге повторяться в соответствии с принципом «ячейки» . Как следствие, последовательности шаблонов гороха всегда в конечном итоге являются периодическими .
См. также [ править ]
Примечания [ править ]
- ↑ Перейти обратно: Перейти обратно: а б n может быть любой цифрой 4 или выше.
Ссылки [ править ]
- ↑ Перейти обратно: Перейти обратно: а б с д Конвей, Дж. Х. (январь 1986 г.). «Странная и чудесная химия аудиоактивного распада» (PDF) . Эврика . 46 : 5–16. Перепечатано как Конвей, Дж. Х. (1987). «Странная и чудесная химия аудиоактивного распада». В обложке, Томас М.; Гопинатх, Б. (ред.). Открытые проблемы коммуникации и вычислений . Спрингер-Верлаг . стр. 173–188. ISBN 0-387-96621-8 .
- ^ Робертс, Шивон (2015). Гений в игре: любопытный ум Джона Хортона Конвея . Блумсбери . ISBN 978-1-62040-593-2 .
- ^ Числа «Посмотри и скажи» (с участием Джона Конвея) - Numberphile на YouTube
- ^ Conway Sequence , MathWorld , доступ онлайн 4 февраля 2011 г.
- ↑ Перейти обратно: Перейти обратно: а б с д и Мартин, Оскар (2006). «Биохимия «Посмотри и скажи: экспоненциальная РНК и многоцепочечная ДНК» (PDF) . Американский математический ежемесячник . 113 (4). Математическая ассоциация Америки: 289–307. дои : 10.2307/27641915 . ISSN 0002-9890 . JSTOR 27641915 . Архивировано из оригинала (PDF) 24 декабря 2006 г. Проверено 6 января 2010 г.
- ^ Экхад, С.Б., Зейлбергер, Д.: Доказательство утраченной космологической теоремы Конвея , Электронные объявления об исследованиях Американского математического общества, 21 августа 1997 г., Vol. 5, стр. 78–82. Проверено 4 июля 2011 г.
- ^ Варди, Илан (1991). Вычислительные развлечения в системе Mathematica . Аддисон-Уэсли . ISBN 0-201-52989-0 .
- ^ Последовательность Роберта Морриса
- ^ Часто задаваемые вопросы о числовой последовательности Морриса
Внешние ссылки [ править ]
- Конвей рассказывает об этой последовательности и говорит, что ему потребовались некоторые объяснения, чтобы понять эту последовательность.
- многих языках программирования. на Реализации Rosetta Code
- Вайсштейн, Эрик В. «Посмотри и скажи последовательность» . Математический мир .
- Генератор последовательности «Посмотри и скажи» p
- Последовательность OEIS A014715 (десятичное расширение константы Конвея)
- Вывод полинома Конвея степени-71 «посмотри и скажи»
