Главная
Новости
Строительство
Ремонт
Дизайн и интерьер
Полезные советы




29.12.2022


29.12.2022


23.12.2022


25.11.2022


08.11.2022


08.11.2022





Яндекс.Метрика





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

16.01.2023

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

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 {displaystyle L_{n}} обозначает длину n-го члена последовательности, то существует предел отношения L n + 1 L n {displaystyle {frac {L_{n+1}}{L_{n}}}} :

lim n → ∞ L n + 1 L n = λ {displaystyle lim _{n o infty }{frac {L_{n+1}}{L_{n}}}=lambda } .

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

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

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

x 71 − x 69 − 2 x 68 − x 67 + 2 x 66 + 2 x 65 + x 64 − x 63 − x 62 − x 61 − x 60 − x 59 + 2 x 58 + 5 x 57 + 3 x 56 − 2 x 55 − 10 x 54 − 3 x 53 − 2 x 52 + 6 x 51 + 6 x 50 + x 49 + 9 x 48 − 3 x 47 − 7 x 46 − 8 x 45 − 8 x 44 + 10 x 43 + 6 x 42 + 8 x 41 − 5 x 40 − 12 x 39 + 7 x 38 − 7 x 37 + 7 x 36 + x 35 − 3 x 34 + 10 x 33 + x 32 − 6 x 31 − 2 x 30 − 10 x 29 − 3 x 28 + 2 x 27 + 9 x 26 − 3 x 25 + 14 x 24 − 8 x 23 − 7 x 21 + 9 x 20 + 3 x 19 − 4 x 18 − 10 x 17 − 7 x 16 + 12 x 15 + 7 x 14 + 2 x 13 − 12 x 12 − 4 x 11 − 2 x 10 + 5 x 9 + x 7 − 7 x 6 + 7 x 5 − 4 x 4 + 12 x 3 − 6 x 2 + 3 x − 6 {displaystyle {egin{aligned}&,,,,,,,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&&-6end{aligned}}}

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

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

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

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


Имя:*
E-Mail:
Комментарий: