Последовательность Gijswijts - Gijswijts sequence - Wikipedia

В математика, Последовательность Гийсвейта (названный в честь Дион Гийсвейт к Нил Слоан[1]) это самоописывающий последовательность где каждый член подсчитывает максимальное количество повторяющихся блоков чисел в последовательности, непосредственно предшествующей этому термину.

Последовательность начинается с:

1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 1, ... (последовательность A090822 в OEIS )

Последовательность аналогична по определению Последовательность Колакоски, но вместо подсчета самой длинной серии отдельных терминов в последовательности подсчитывается самая длинная серия блоков терминов любой длины. Последовательность Гийсвейта известна своей чрезвычайно медленной скоростью роста. Например, первые 4 появляются в 220-м члене, а первые 5 появляются рядом с третий срок.[1]

Определение

Процесс создания терминов в последовательности можно определить, рассматривая последовательность как серию букв в алфавит из натуральные числа:

  1. , и
  2. , куда - наибольшее натуральное число такое, что слово можно записать в виде для некоторых слов и , с имеющий ненулевую длину.

Последовательность основание -агностический. То есть, если будет обнаружена серия из 10 повторяющихся блоков, следующим термином в последовательности будет одно число 10, а не 1, за которым следует 0.

Объяснение

Последовательность начинается с 1 по определению. Тогда 1 во втором члене представляет длину 1 блока единиц, который находится непосредственно перед ним в первом члене. 2 в третьем члене представляет длину 2 блока единиц в первом и втором члене. В этот момент последовательность уменьшается в первый раз: 1 в четвертом члене представляет длину 1 блока из 2 секунд в 3-м члене, а также длину 1 блока «1, 2», охватывающего второй и третий срок. Нет блока любой повторяющейся последовательности, непосредственно предшествующей четвертому члену, длина которого превышает длину 1. Блок из двух единиц в первом и втором члене не может рассматриваться как четвертый член, потому что они разделены другим числом в третьем члене. .

1 в пятом члене представляет длину 1 «повторяющихся» блоков «1» и «2, 1» и «1, 2, 1» и «1, 1, 2, 1», которые непосредственно предшествуют пятому члену. Ни один из этих блоков не повторяется более одного раза, поэтому пятый член равен 1. 2 в шестом члене представляет длину повторяющегося блока единиц, непосредственно ведущих к шестому члену, а именно единиц в 4-м и 5-м членах. Цифра 2 в седьмом члене представляет 2 повторения блока «1, 1, 2», охватывающего термины 1-3, а затем 4-6. Это "трехзначное слово" встречается дважды, непосредственно перед седьмым термином, поэтому значение седьмого члена равно 2.

Цифра 2 в восьмом члене представляет собой длину повторяющегося блока двоек, непосредственно ведущих к восьмому члену, а именно двоек в шестом и седьмом членах. Тройка в 9-м члене представляет собой троекратный блок одиночных двойок, непосредственно ведущих к 9-му члену, а именно двойки в шестом, седьмом и восьмом членах.

Характеристики

Только ограниченное исследование было сосредоточено на последовательности Гийсвейта. Таким образом, очень мало доказано о последовательности, и многие открытые вопросы остаются нерешенными.

Уровень роста

Учитывая, что 5 не появляется, пока около методы перебора никогда не найдут первое вхождение слова больше 4. Однако было доказано, что последовательность содержит все натуральные числа.[2] Точная скорость роста неизвестна, но предполагается, что она будет расти. сверхлогарифмически, с первым появлением любого естественного расположен рядом .[3]

Средняя стоимость

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

Точно так же плотность любого данного натурального числа в последовательности неизвестно.[1]

Рекурсивная структура

Последовательность можно разбить на дискретные «блочные» и «склеивающие» последовательности, которые можно использовать для рекурсивного построения последовательности. Например, на базовом уровне мы можем определить и как первый блок и последовательность клея соответственно. Вместе мы можем увидеть, как они образуют начало последовательности:

Следующим шагом будет рекурсивное построение последовательности. Определять . Отметив, что последовательность начинается с , мы можем определить клеящую нить который дает:

Мы назначили к определенной последовательности, которая дает свойство, что также встречается в верхней части последовательности.

Этот процесс можно продолжать бесконечно с . Оказывается, мы можем обнаружить клеящую нить отмечая, что никогда не будет 1, и что он остановится, как только достигнет первой 1, чтобы следовать .[3] Также было доказано, что последовательность Гийсвейта может быть построена таким образом до бесконечности, то есть и всегда конечны по длине для любого .[2]

Умные манипуляции с связующими последовательностями в этой рекурсивной структуре могут быть использованы для демонстрации того, что последовательность Гийсвейта, помимо других свойств последовательности, содержит все натуральные числа.

Смотрите также

Рекомендации

  1. ^ а б c Слоан, Н. Дж. А. (ред.). "Последовательность A090822 (последовательность Гийсвейта: a (1) = 1; для n> 1, a (n) = наибольшее целое число k такое, что слово a (1) a (2) ... a (n-1) имеет форма xy ^ k для слов x и y (где y имеет положительную длину), т. е. максимальное количество повторяющихся блоков в конце последовательности на данный момент) ". В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
  2. ^ а б Гийсвейт, округ Колумбия (2006). «Медленно растущая последовательность, определяемая необычным повторением». arXiv:математика / 0602498.
  3. ^ а б Слоан, Нил. «Семь потрясающих последовательностей» (PDF). AT&T Shannon Lab. п. 3.

внешняя ссылка

OEIS последовательность A090822 (последовательность Гийсвейта)