Последовательность «Посмотри-и-скажи» — это последовательность чисел, начинающаяся следующим образом:
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, …
Основные свойства
Рост
Последовательность растёт бесконечно. Фактически, любой вариант последовательности с целым начальным числом будет расти бесконечно. Исключение составляет последовательность:
Ограничение использующихся цифр
Никакие цифры, кроме 1, 2 и 3 не встречаются в последовательности, если начальное число не содержит других цифр или группы более чем из трёх цифр[2].
Рост длины чисел
В среднем, числа вырастают на 30 % за итерацию. Если обозначает длину n-го члена последовательности, то существует предел отношения :
.
Здесь λ = 1.303577269034… — постоянная Конвея[2]. Тот же результат справедлив для любого варианта последовательности с начальным числом, отличным от 22.
Многочлен, возвращающий константу Конвея
Константа Конвея — это единственный вещественный корень многочлена:
В своей оригинальной статье Конвей совершает ошибку, написав «-» вместо «+» перед . Но значение λ, данное в его статье, верно[3].
Популяризация
Последовательность «Посмотри-и-скажи» также известна как последовательность чисел Морриса в честь криптографа Роберта Морриса[en]. Иногда упоминается как «яйцо кукушки» из-за головоломки «Какое следующее число в последовательности 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 для больших начальных чисел (например, «сто единиц»).
Учитывая, что эта последовательность бесконечна и длина её ограничена, она должна в конечном итоге повториться, по принципу Дирихле. Как следствие, эти последовательности всегда периодические.
См. также
Примечания
- ↑ John Horton Conway. The Weird and Wonderful Chemistry of Audioactive Decay (англ.) // Eureka. — 1986. — January (vol. 46). — P. 5—16. Архивировано 11 октября 2014 года.
- 1 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 года.
- ↑ Ilan Vardi. Computational Recreation in Mathematica.
- ↑ Ascending Pea Pattern generator.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .