Последовательность Гийсвита — последовательность, начинающаяся с
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. Каждый последующий член — наибольшее число такое, что строку, образованную путём конкатенации все предыдущих членов («букв»), можно представить в виде (то есть ), где и — строки, причём имеет ненулевую длину. Многозначные числа в последовательности следует воспринимать как числа, а не как их отдельные цифры. То есть, например, число 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. Однако, было доказано, что в последовательности встречается каждое натуральное число. Точная скорость роста неизвестна, но есть предположение, что в первый раз натуральное число появляется в последовательности на позиции .
Среднее значение Хотя было доказано, что любое натуральное число встречается в последовательности, было выдвинуто предположение, что последовательность может иметь среднее значение. Формально, гипотеза такова:
где — -й член последовательности Гийсвита.
Частота появления любого натурального числа в последовательности также неизвестна.
Рекурсивная структура Последовательность может быть разбита на дискретные последовательности — «блок» и «клей» — которые могут быть использованы для рекурсивного создания последовательности.
Вначале определим и как первые последовательности «блока» и «клея» соответственно. Они формируют первые члены последовательности:
.
Далее рекурсивно определим . Тогда строка «клея» примет вид . Теперь генерируемая последовательность:
.
Обратите внимание, что строку «клея» мы определили не рекурсивно, а присвоили ей конкретное значение, которое мы получаем из определения последовательности Гийсвита.
Таким образом, мы можем определить формулу для «блоков»: . Строки «клея» получаем, достраивая последовательность по определению, до тех пор, пока не достигнем 1.
См. также Последовательность «Посмотри-и-скажи» Последовательность Колакоски
Примечания
Категория:Целочисленные последовательности