Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску
Линии показывают рост количества цифр в последовательностях look-and-say с начальными точками 23 (красный), 1 (синий), 13 (фиолетовый), 312 (зеленый). Эти линии (когда они представлены в логарифмической вертикальной шкале ) стремятся к прямым линиям, наклон которых совпадает с постоянной Конвея.

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

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ... (последовательность A005150 в OEIS ).

Чтобы сгенерировать член последовательности из предыдущего члена, считайте цифры предыдущего члена, считая количество цифр в группах одной и той же цифры. Например:

  • 1 читается как «единица 1» или 11.
  • 11 читается как «две единицы» или 21.
  • 21 читается как «один 2, затем один 1» или 1211.
  • 1211 читается как «одна 1, одна 2, затем две единицы» или 111221.
  • 111221 читается как «три единицы, две двойки, затем одна единица» или 312211.

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

Идея последовательности «смотрю и говори» аналогична идее кодирования длин серий .

Если начать с любой цифры d от 0 до 9, то d будет оставаться последней цифрой последовательности неопределенно долго. Для любого d, отличного от 1, последовательность начинается следующим образом:

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

Илан Варди назвал эту последовательность, начиная с d = 3, последовательностью Конвея (последовательность A006715 в OEIS ). (для d = 2 см. OEIS :  A006751 ) [2]

Основные свойства [ править ]

Корни полинома Конвея на комплексной плоскости . Константа Конвея обозначается греческой буквой лямбда ( λ ).

Рост [ править ]

Последовательность растет бесконечно. Фактически, любой вариант, определенный начиная с другого целого начального числа, (в конечном итоге) также будет расти бесконечно, за исключением вырожденной последовательности: 22, 22, 22, 22,… (последовательность A010861 в OEIS ) [3]

Ограничение наличия цифр [ править ]

Никакие цифры, кроме 1, 2 и 3, не появляются в последовательности, если только начальное число не содержит такую ​​цифру или серию из более чем трех одинаковых цифр. [3]

Космологический распад [ править ]

Космологическая теорема Конвея утверждает, что каждая последовательность в конечном итоге распадается («распадается») на последовательность «атомарных элементов», которые представляют собой конечные подпоследовательности, которые никогда больше не взаимодействуют со своими соседями. Есть 92 элемента, содержащих только цифры 1, 2 и 3, которые Джон Конвей назвал в честь химических элементов вплоть до урана, назвав последовательность аудиоактивной . Также есть два « трансурановых » элемента для каждой цифры, кроме 1, 2 и 3. [3] [4]

Рост в длине [ править ]

В конечном итоге сроки вырастают примерно на 30% за поколение. В частности, если L n обозначает количество цифр n -го члена последовательности, то предел отношения существует и определяется выражением

где λ = 1,303577269034 ... (последовательность A014715 в OEIS ) - алгебраическое число степени 71. [3] Этот факт был доказан Конвеем, а постоянная λ известна как константа Конвея . Тот же результат сохраняется для каждого варианта последовательности, начиная с любого начального числа, кроме 22.

Константа Конвея как корень многочлена [ править ]

Константа Конвея является единственным положительным вещественным корнем следующего многочлена : (последовательность A137275 в OEIS )

В своей оригинальной статье Конвей дает неправильное значение для этого многочлена, написав - вместо + перед . [5] Однако значение λ, указанное в его статье, является правильным.

Популяризация [ править ]

Последовательность «взгляни и скажи» также широко известна как последовательность чисел Морриса , в честь криптографа Роберта Морриса , и головоломки «Какое будет следующее число в последовательности 1, 11, 21, 1211, 111221?» иногда упоминается как Яйцо кукушки из описания Морриса в книге Клиффорда Столла «Яйцо кукушки» . [6] [7]

Варианты [ править ]

Есть много возможных вариантов правила, используемого для создания последовательности «посмотрю и скажи». Например, чтобы сформировать «образец горошины», читают предыдущий термин и подсчитывают все экземпляры каждой цифры, перечисленные в порядке их первого появления, а не только те, которые встречаются в последовательном блоке. Таким образом, начиная с семени 1, паттерн гороха продолжается 1, 11 («одна 1»), 21 («две единицы»), 1211 («одна 2 и одна 1»), 3112 («три единицы и одна 2». ), 132112 («одна тройка, две единицы и одна двойка»), 311322 («три единицы, одна тройка и две двойки») и т. Д. Эта версия паттерна горошек в конечном итоге формирует цикл с двумя членами 23322114 и 32232114. [8]

Возможны и другие варианты рисунка горошек; например, вместо того, чтобы читать цифры по мере их появления, можно было бы читать их в возрастающем порядке. В этом случае термин, следующий за 21, будет 1112 («одна 1, одна 2»), а термин, следующий за 3112, будет 211213 («две единицы, одна 2 и одна 3»).

Эти последовательности несколько заметно отличаются от последовательности «посмотрю и скажи». Примечательно, что, в отличие от последовательностей Конвея, данный термин паттерна гороха не определяет однозначно предыдущий термин. Более того, для любого семени образец гороха дает члены ограниченной длины. Эта граница обычно не превышает 2 * основание + 2 цифры и может превышать длину только 3 * цифр счисления для вырожденных длинных начальных начальных чисел («100 единиц и т. Д.»). Для этих максимально ограниченных случаев отдельные элементы последовательности принимают форму a0b1c2d3e4f5g6h7i8j9 для десятичной дроби, где буквы здесь являются заполнителями для количества цифр из предыдущего элемента последовательности. Учитывая, что эта последовательность бесконечна, а длина ограничена, она должна в конечном итоге повториться из-запринцип ящика . Как следствие, эти последовательности всегда в конечном итоге периодичны .

См. Также [ править ]

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

Ссылки [ править ]

  1. ↑ Конвей, Джон (январь 1986). «Странная и чудесная химия аудиоактивного распада» . Эврика . 46 : 5–16. Архивировано из оригинала на 2014-10-11.
  2. ^ Conway Sequence , MathWorld , доступ на сайте 4 февраля 2011 г.
  3. ^ a b c d Мартин, Оскар (2006). «Простая биохимия: экспоненциальная РНК и многоцепочечная ДНК» (PDF) . Американский математический ежемесячник . Математическая ассоциация Америки. 113 (4): 289–307. DOI : 10.2307 / 27641915 . ISSN 0002-9890 . Архивировано из оригинального (PDF) 24 декабря 2006 года . Проверено 6 января 2010 года .  
  4. ^ Ekhad, SB, Zeilberger, D .: Доказательство утерянных космологических теорем Конвея , электронные исследования Анонсов Американского математического общества, 21 августа 1997, Vol. 5. С. 78–82. Проверено 4 июля 2011 года.
  5. ^ Илан Варди, Вычислительная отдых в Mathematica
  6. ^ Последовательность Роберта Морриса
  7. ^ Часто задаваемые вопросы о числовой последовательности Морриса
  8. ^ "Генератор восходящего гороха" . codegolf.stackexchange.com . Проверено 7 мая 2016 .

Внешние ссылки [ править ]

  • Конвей говорит об этой последовательности и говорит, что ему потребовались некоторые объяснения, чтобы понять последовательность.
  • Реализации на многих языках программирования на Rosetta Code
  • Вайсштейн, Эрик В. «Посмотри и скажи последовательность» . MathWorld .
  • Генератор последовательности Look and Say p
  • Последовательность OEIS A014715 (десятичное разложение константы Конвея)
  • Вывод многочлена степени-71 Конвея "взгляни и скажи"