Последовательность «Посмотри-и-скажи» — это последовательность чисел, начинающаяся следующим образом:
1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211,… (последовательность A005150 в OEIS).
Каждое последующее число генерируется из предыдущего путём конкатенации цифры, из которой состоит группа одинаковых цифр и количества цифр в этой группе, для каждой группы одинаковых цифр в числе. Например:
1 читается как «одна единица», то есть 11 11 читается как «две единицы», то есть 21 21 читается как «одна двойка, одна единица», то есть 1211 1211 читается как «одна единица, одна двойка, две единицы», то есть 111221 111221 читается как «три единицы, две двойки, одна единица», то есть 312211 312211 читается как «одна тройка, одна единица, две двойки, две единицы», то есть 13112221
Последовательность «посмотри-и-скажи» была предложена Джоном Конвеем.
Для произвольной цифры d, кроме единицы, в качестве начальной, последовательность принимает вид:
d, 1d, 111d, 311d, 13211d, 111312211d, 31131122211d, …
Основные свойства
Рост Последовательность растёт бесконечно. Фактически, любой вариант последовательности с целым начальным числом будет расти бесконечно. Исключение составляет последовательность:
22, 22, 22, 22, 22, … (последовательность A010861 в OEIS).
Ограничение использующихся цифр Никакие цифры, кроме 1, 2 и 3 не встречаются в последовательности, если начальное число не содержит других цифр или группы более чем из трёх цифр.
Рост длины чисел В среднем, числа вырастают на 30 % за итерацию. Если обозначает длину n-го члена последовательности, то существует предел отношения :
.
Здесь λ = 1.303577269034… — постоянная Конвея (OEIS A014715). Тот же результат справедлив для любого варианта последовательности с начальным числом, отличным от 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 для больших начальных чисел (например, «сто единиц»).
Учитывая, что эта последовательность бесконечна и длина её ограничена, она должна в конечном итоге повториться, по принципу Дирихле. Как следствие, эти последовательности всегда периодические.
См. также Последовательность Колакоски Последовательность Гийсвита
Примечания
Категория:Целочисленные последовательности Категория:Джон Конвей