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

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

Графики показывают рост количества цифр в последовательности «Посмотри-и-скажи» с начальными числами: 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

Последовательность «посмотри-и-скажи» была предложена Джоном Конвеем[1].

Для произвольной цифры d, кроме единицы, в качестве начальной, последовательность принимает вид:

d, 1d, 111d, 311d, 13211d, 111312211d, 31131122211d, …

Основные свойства
Корни многочлена Конвея на комплексной плоскости

Рост

Последовательность растёт бесконечно. Фактически, любой вариант последовательности с целым начальным числом будет расти бесконечно. Исключение составляет последовательность:

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 для больших начальных чисел (например, «сто единиц»).

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

См. также

Примечания
  1. John Horton Conway. The Weird and Wonderful Chemistry of Audioactive Decay (англ.) // Eureka. — 1986. — January (vol. 46). — P. 5—16. Архивировано 11 октября 2014 года.
  2. Oscar Martin. Look-and-Say Biochemistry: Exponential RNA and Multistranded DNA (англ.) // American Mathematical Monthly. — 2006. — Vol. 113, no. 4. — P. 289—307. — ISSN 0002-9890. Архивировано 24 декабря 2006 года.
  3. Ilan Vardi. Computational Recreation in Mathematica.
  4. Ascending Pea Pattern generator.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.