Графики показывают рост количества цифр в последовательности «Посмотри-и-скажи» с начальными числами: 1 (синий), 13 (фиолетовый), 23 (красный) и 312 (зелёный). Эти графики стремятся к прямым линиям (вертикальная шкала представлена в логарифмическом масштабе)
Последовательность «Посмотри-и-скажи» — это последовательность чисел, начинающаяся следующим образом:
Каждое последующее число генерируется из предыдущего путём конкатенации цифры, из которой состоит группа одинаковых цифр и количества цифр в этой группе, для каждой группы одинаковых цифр в числе. Например:
1 читается как «одна единица», то есть 11
11 читается как «две единицы», то есть 21
21 читается как «одна двойка, одна единица», то есть 1211
1211 читается как «одна единица, одна двойка, две единицы», то есть 111221
111221 читается как «три единицы, две двойки, одна единица», то есть 312211
312211 читается как «одна тройка, одна единица, две двойки, две единицы», то есть 13112221
Последовательность «посмотри-и-скажи» была предложена Джоном Конвеем[1].
Для произвольной цифры d, кроме единицы, в качестве начальной, последовательность принимает вид:
Последовательность растёт бесконечно. Фактически, любой вариант последовательности с целым начальным числом будет расти бесконечно. Исключение составляет последовательность:
22, 22, 22, 22, 22, … (последовательность A010861 в OEIS).
Ограничение использующихся цифр
Никакие цифры, кроме 1, 2 и 3 не встречаются в последовательности, если начальное число не содержит других цифр или группы более чем из трёх цифр[2].
Рост длины чисел
В среднем, числа вырастают на 30 % за итерацию. Если обозначает длину n-го члена последовательности, то существует предел отношения :
.
Здесь λ = 1.303577269034… — постоянная Конвея[2]. Тот же результат справедлив для любого варианта последовательности с начальным числом, отличным от 22.
Многочлен, возвращающий константу Конвея
Константа Конвея — это единственный положительный вещественный корень многочлена:
В своей оригинальной статье Конвей совершает ошибку, написав «−» вместо «+» перед . Но значение λ, данное в его статье, верно[3].
Популяризация
Последовательность «Посмотри-и-скажи» также известна как последовательность чисел Морриса в честь криптографа Роберта Морриса[англ.]. Иногда упоминается как «яйцо кукушки» из-за головоломки «Какое следующее число в последовательности 1, 11, 21, 1211, 111221?», описанной Моррисом в книге Клиффорда Столла «Яйцо Кукушки».
Вариации
Существует много вариантов правил для создания последовательностей, подобных «Посмотри-и-скажи». Например, последовательность «pea pattern». Она отличается от «Посмотри-и-скажи» тем, что для получения нового числа в ней нужно подсчитывать все одинаковые цифры в числе. Начиная с числа 1, получим: 1, 11 (одна единица), 21 (две единицы), 1211 (одна двойка, одна единица), 3112 (три единицы, одна двойка), 132112 (одна тройка, две единицы, одна двойка), 312213 (три единицы, две двойки, одна тройка) и т. д. В итоге, последовательность приходит к циклу из двух чисел, 23322114 и 32232114.[4]
Существует другой вариант, отличающийся от «pea pattern» тем, что цифры подсчитываются в порядке возрастания, а не по мере появления. Начиная с единицы, получим последовательность: 1, 11, 21, 1112, 3112, 211213, 312213, …
Эти последовательности имеют примечательные отличия от «Посмотри-и-скажи». В отличие от последовательности Конвея, данный член в «pea pattern» не однозначно определяет предыдущий член. Длина чисел в «pea pattern» ограничена и, для b-ричной системы счисления, не превышает 2b, и достигает 3b для больших начальных чисел (например, «сто единиц»).
Учитывая, что эта последовательность бесконечна и длина её ограничена, она должна в конечном итоге повториться, по принципу Дирихле. Как следствие, эти последовательности всегда периодические.
