Последовательность «Посмотри-и-скажи»

Графики показывают рост количества цифр в последовательности «Посмотри-и-скажи» с начальными числами: 1 (синий), 13 (фиолетовый), 23 (красный) и 312 (зелёный). Эти графики стремятся к прямым линиям (вертикальная шкала представлена в логарифмическом масштабе)

Последовательность «Посмотри-и-скажи» — это последовательность чисел, начинающаяся следующим образом:

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 % за итерацию. Если $L_n$ обозначает длину n-го члена последовательности, то существует предел отношения $\frac{L_{n+1}}{L_n}$:

$\underset{n\to \mathrm{\infty }}{\lim }\frac{L_{n+1}}{L_n}=\lambda$.

Здесь λ = 1.303577269034… — постоянная Конвея. Тот же результат справедлив для любого варианта последовательности с начальным числом, отличным от 22.

Многочлен, возвращающий константу Конвея

Константа Конвея — это единственный положительный вещественный корень многочлена:

$\begin{array}{cccccccccccccccccc}& 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{array}$

В своей оригинальной статье Конвей совершает ошибку, написав «−» вместо «+» перед $x^{35}$. Но значение λ, данное в его статье, верно.

Популяризация

Последовательность «Посмотри-и-скажи» также известна как последовательность чисел Морриса в честь криптографа Шаблон:Нп5. Иногда упоминается как «яйцо кукушки» из-за головоломки «Какое следующее число в последовательности 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 для больших начальных чисел (например, «сто единиц»).

Учитывая, что эта последовательность бесконечна и длина её ограничена, она должна в конечном итоге повториться, по принципу Дирихле. Как следствие, эти последовательности всегда периодические.

См. также

• Последовательность Колакоски
• Последовательность Гийсвита