Русская Википедия:Последовательность Гийсвита
Последовательность Гийсвита — последовательность, начинающаяся с
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>k</math> такое, что строку, образованную путём конкатенации все предыдущих членов («букв»), можно представить в виде <math>X Y^k</math>(то есть <math>X \underbrace{ YYY\dots Y }_{k}</math>), где <math>X</math> и <math>Y</math> — строки, причём <math>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
и т. д.
Свойства
Над последовательностью Гийсвита проводятся ограниченные исследования. Из-за этого она остаётся малоизученной, и многие вопросы насчёт неё остаются открытымиШаблон:Нет АИ.
Скорость роста
Учитывая, что число 5 не встречается в последовательности примерно до 101023-й позиции, методом «грубой силы» вряд ли удастся найти числа больше, чем 4. Однако, было доказано, что в последовательности встречается каждое натуральное число[2]. Точная скорость роста неизвестна, но есть предположение, что в первый раз натуральное число <math>n</math> появляется в последовательности на позиции <math>2^{2^{3^{4^{\cdot^{\cdot^{\cdot^{n-1}}}}}}}</math>[3].
Среднее значение
Хотя было доказано, что любое натуральное число встречается в последовательности, было выдвинуто предположение, что последовательность может иметь среднее значение. Формально, гипотеза таковаШаблон:Нет АИ:
<math>\lim_{n \to \infty} \frac {1} {n} \sum_{i=1}^n G(i) < \infin</math>
где <math>G(n)</math> — <math>n</math>-й член последовательности Гийсвита.
Частота появления любого натурального числа в последовательности также неизвестна.
Рекурсивная структура
Последовательность может быть разбита на дискретные последовательности — «блок» и «клей» — которые могут быть использованы для рекурсивного создания последовательности.
Вначале определим <math>B_1 = 1</math> и <math>S_1 = 2</math> как первые последовательности «блока» и «клея» соответственно. Они формируют первые члены последовательности:
<math>B_1B_1S_1 = 1,1,2</math>.
Далее рекурсивно определим <math>B_2 = B_1B_1S_1</math>. Тогда строка «клея» примет вид <math>S_2 = 2,3,3</math>. Теперь генерируемая последовательность:
<math>B_2B_2S_2 = 1,1,2,1,1,2,2,2,3</math>.
Обратите внимание, что строку «клея» <math>S_2</math> мы определили не рекурсивно, а присвоили ей конкретное значение, которое мы получаем из определения последовательности Гийсвита.
Таким образом, мы можем определить формулу для «блоков»: <math>B_{n+1} = B_nB_nS_n</math>. Строки «клея» <math>S_n</math> получаем, достраивая последовательность по определению, до тех пор, пока не достигнем 1.
См. также
Примечания
