Последовательность Гийсвита
Последовательность Гийсвита — последовательность, начинающаяся с
1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 1, … (последовательность A090822 в OEIS).
Последовательность названа создателем OEIS Нилом Слоуном в честь Д. Гийсвита (D. C. Gijswijt). Эта последовательность в первую очередь интересна благодаря своей медленной скорости роста: число 4 в первый раз встречается на позиции 220, а число 5 — вблизи позиции 101023[1].
Описание
Представим члены последовательность в виде букв алфавита, представленных натуральными числами. Первый член последовательности — 1. Каждый последующий член — наибольшее число [math]\displaystyle{ k }[/math] такое, что строку, образованную путём конкатенации все предыдущих членов («букв»), можно представить в виде [math]\displaystyle{ X Y^k }[/math](то есть [math]\displaystyle{ X \underbrace{ YYY\dots Y }_{k} }[/math]), где [math]\displaystyle{ X }[/math] и [math]\displaystyle{ Y }[/math] — строки, причём [math]\displaystyle{ Y }[/math] имеет ненулевую длину. Многозначные числа в последовательности следует воспринимать как числа, а не как их отдельные цифры. То есть, например, число 10 будет использовано как цельный символ «10», а не как «1» и «0».
Пример генерации последовательности:
- На первой итерации, первый член равен 1
- Строку «1» представляем как «1»1, следующий член — 1
- Строку «11» представляем как «1»2, следующий член — 2
- Строку «112» представляем как «112»1, следующий член — 1
- Строку «11211» представляем как «112»"1"2, следующий член — 2
- Строку «112112» представляем как «112»2, следующий член — 2
- Строку «1121122» представляем как «11211»"2"2, следующий член — 2
- Строку «11211222» представляем как «112112»"2"3, следующий член — 3
- Строку «112112223» представляем как «112112223»1, следующий член — 1
и т. д.
Свойства
Над последовательностью Гийсвита проводятся ограниченные исследования. Из-за этого она остаётся малоизученной, и многие вопросы насчёт неё остаются открытыми[источник не указан 2294 дня].
Скорость роста
Учитывая, что число 5 не встречается в последовательности примерно до 101023-й позиции, методом «грубой силы» вряд ли удастся найти числа больше, чем 4. Однако, было доказано, что в последовательности встречается каждое натуральное число[2]. Точная скорость роста неизвестна, но есть предположение, что в первый раз натуральное число [math]\displaystyle{ n }[/math] появляется в последовательности на позиции [math]\displaystyle{ 2^{2^{3^{4^{\cdot^{\cdot^{\cdot^{n-1}}}}}}} }[/math][3].
Среднее значение
Хотя было доказано, что любое натуральное число встречается в последовательности, было выдвинуто предположение, что последовательность может иметь среднее значение. Формально, гипотеза такова[источник не указан 2294 дня]:
[math]\displaystyle{ \lim_{n \to \infty} \frac {1} {n} \sum_{i=1}^n G(i) \lt \infin }[/math]
где [math]\displaystyle{ G(n) }[/math] — [math]\displaystyle{ n }[/math]-й член последовательности Гийсвита.
Частота появления любого натурального числа в последовательности также неизвестна.
Рекурсивная структура
Последовательность может быть разбита на дискретные последовательности — «блок» и «клей» — которые могут быть использованы для рекурсивного создания последовательности.
Вначале определим [math]\displaystyle{ B_1 = 1 }[/math] и [math]\displaystyle{ S_1 = 2 }[/math] как первые последовательности «блока» и «клея» соответственно. Они формируют первые члены последовательности:
[math]\displaystyle{ B_1B_1S_1 = 1,1,2 }[/math].
Далее рекурсивно определим [math]\displaystyle{ B_2 = B_1B_1S_1 }[/math]. Тогда строка «клея» примет вид [math]\displaystyle{ S_2 = 2,3,3 }[/math]. Теперь генерируемая последовательность:
[math]\displaystyle{ B_2B_2S_2 = 1,1,2,1,1,2,2,2,3 }[/math].
Обратите внимание, что строку «клея» [math]\displaystyle{ S_2 }[/math] мы определили не рекурсивно, а присвоили ей конкретное значение, которое мы получаем из определения последовательности Гийсвита.
Таким образом, мы можем определить формулу для «блоков»: [math]\displaystyle{ B_{n+1} = B_nB_nS_n }[/math]. Строки «клея» [math]\displaystyle{ S_n }[/math] получаем, достраивая последовательность по определению, до тех пор, пока не достигнем 1.
См. также
Примечания
- ↑ Sloane, N.J.A. (ed.). Sequence A090822. Онлайн Энциклопедия Целочисленных Последовательностей. OEIS Foundation. Дата обращения: 15 августа 2018. Архивировано 16 августа 2018 года.
- ↑ D. C. Gijswijt. A Slow-Growing Sequence Defined by an Unusual Recurrence. arXiv.org (2006). Дата обращения: 15 августа 2018. Архивировано 16 августа 2018 года.
- ↑ Neil Sloane. Seven Staggering Sequences 3. Дата обращения: 15 августа 2018. Архивировано 28 июня 2018 года.