Русская Википедия:Последовательность «Посмотри-и-скажи»
Последовательность «Посмотри-и-скажи» — это последовательность чисел, начинающаяся следующим образом:
1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211,… (последовательность A005150 в OEIS).
Каждое последующее число генерируется из предыдущего путём конкатенации цифры, из которой состоит группа одинаковых цифр и количества цифр в этой группе, для каждой группы одинаковых цифр в числе. Например:
- 1 читается как «одна единица», то есть 11
- 11 читается как «две единицы», то есть 21
- 21 читается как «одна двойка, одна единица», то есть 1211
- 1211 читается как «одна единица, одна двойка, две единицы», то есть 111221
- 111221 читается как «три единицы, две двойки, одна единица», то есть 312211
- 312211 читается как «одна тройка, одна единица, две двойки, две единицы», то есть 13112221
Последовательность «посмотри-и-скажи» была предложена Джоном Конвеем[1].
Для произвольной цифры d, кроме единицы, в качестве начальной, последовательность принимает вид:
d, 1d, 111d, 311d, 13211d, 111312211d, 31131122211d, …
Основные свойства
Рост
Последовательность растёт бесконечно. Фактически, любой вариант последовательности с целым начальным числом будет расти бесконечно. Исключение составляет последовательность:
22, 22, 22, 22, 22, … (последовательность A010861 в OEIS).
Ограничение использующихся цифр
Никакие цифры, кроме 1, 2 и 3 не встречаются в последовательности, если начальное число не содержит других цифр или группы более чем из трёх цифр[2].
Рост длины чисел
В среднем, числа вырастают на 30 % за итерацию. Если <math>L_n</math> обозначает длину n-го члена последовательности, то существует предел отношения <math>\frac {L_{n+1}} {L_n}</math>:
<math>\lim_{n \to \infty} \frac {L_{n+1}} {L_n} = \lambda</math>.
Здесь λ = 1.303577269034… — постоянная Конвея[2]. Тот же результат справедлив для любого варианта последовательности с начальным числом, отличным от 22.
Многочлен, возвращающий константу Конвея
Константа Конвея — это единственный положительный вещественный корень многочлена:
<math>\begin{align} &\,\,\,\,\,\,\, 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{align}</math>
В своей оригинальной статье Конвей совершает ошибку, написав «−» вместо «+» перед <math>x^{35}</math>. Но значение λ, данное в его статье, верно[3].
Популяризация
Последовательность «Посмотри-и-скажи» также известна как последовательность чисел Морриса в честь криптографа Шаблон:Нп5. Иногда упоминается как «яйцо кукушки» из-за головоломки «Какое следующее число в последовательности 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 для больших начальных чисел (например, «сто единиц»).
Учитывая, что эта последовательность бесконечна и длина её ограничена, она должна в конечном итоге повториться, по принципу Дирихле. Как следствие, эти последовательности всегда периодические.
См. также
Примечания
