WikiSort.ru - Не сортированное

Последовательность Гийвеста — последовательность, начинающаяся с

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 — вблизи позиции 10^10²³^[1].

Описание

Представим члены последовательность в виде букв алфавита, представленных натуральными числами. Первый член последовательности — 1. Каждый последующий член — наибольшее число $k$ такое, что строку, образованную путём конкатенции все предыдущих членов («букв»), можно представить в виде $XY^{k}$ (то есть $X\underbrace {YYY\dots Y} _{k}$ ), где $X$ и $Y$ — строки, причём $Y$ имеет ненулевую длину. Многозначные числа в последовательности следует воспринимать как числа, а не как их отдельные цифры. То есть, например, число 10 будет использовано как цельный символ «10», а не как «1» и «0».

Пример генерации последовательности:

На первой итерации, первый член равен 1
Строку «1» представляем как «1»¹, следующий член — 1
Строку «11» представляем как «1»², следующий член — 2
Строку «112» представляем как «112»¹, следующий член — 1
Строку «11211» представляем как «112»"1"², следующий член — 2
Строку «112112» представляем как «112»², следующий член — 2
Строку «1121122» представляем как «11211»"2"², следующий член — 2
Строку «11211222» представляем как «112112»"2"³, следующий член — 3
Строку «112112223» представляем как «112112223»¹, следующий член — 1

и т. д.

Свойства

Над последовательностью Гийвеста проводятся ограниченные исследования. Из-за этого она остаётся малоизученной, и многие вопросы насчёт неё остаются открытыми^{[источник не указан 179 дней]}.

Скорость роста

Учитывая, что число 5 не встречается в последовательности примерно до 10^10²³-й позиции, методом «грубой силы» вряд ли удастся найти числа больше, чем 4. Однако, было доказано, что в последовательности встречается каждое натуральное число^[2]. Точная скорость роста неизвестна, но есть предположение, что в первый раз натуральное число $n$ появляется в последовательности на позиции $2^{2^{3^{4^{\cdot ^{\cdot ^{\cdot ^{n-1}}}}}}}$ ^[3].

Среднее значение

Хотя было доказано, что любое натуральное число встречается в последовательности, было выдвинуто предположение, что последовательность может иметь среднее значение. Формально, гипотеза такова^{[источник не указан 179 дней]}:

$\lim _{n\to \infty }{\frac {1}{n}}\sum _{i=1}^{n}G(i)<\infty$

где $G(n)$ — $n$ -й член последовательности Гийвеста.

Частота появления любого натурального числа в последовательности также неизвестна.

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

Последовательность может быть разбита на дискретные последовательности — «блок» и «клей» — которые могут быть использованы для рекурсивного создания последовательности.

Вначале определим $B_{1}=1$ и $S_{1}=2$ как первые последовательности «блока» и «клея» соответственно. Они формируют первые члены последовательности:

$B_{1}B_{1}S_{1}=1,1,2$ .

Далее рекурсивно определим $B_{2}=B_{1}B_{1}S_{1}$ . Тогда строка «клея» примет вид $S_{2}=2,3,3$ . Теперь генерируемая последовательность:

$B_{2}B_{2}S_{2}=1,1,2,1,1,2,2,2,3$ .

Обратите внимание, что строку «клея» $S_{2}$ мы определили не рекурсивно, а присвоили ей конкретное значение, которое мы получаем из определения последовательности Гийвеста.

Таким образом, мы можем определить формулу для «блоков»: $B_{n+1}=B_{n}B_{n}S_{n}$ . Строки «клея» $S_{n}$ получаем, достраивая последовательность по определению, до тех пор, пока не достигнем 1.

См. также

Примечания

↑ Sloane, N.J.A. (ed.). Sequence A090822 (неопр.). Онлайн Энциклопедия Целочисленных Последовательностей. OEIS Foundation.
↑ D. C. Gijswijt. A Slow-Growing Sequence Defined by an Unusual Recurrence (неопр.). arXiv.org (2006).
↑ Neil Sloane. Seven Staggering Sequences (неопр.) 3.

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии

[1] Sloane, N.J.A. (ed.). Sequence A090822 (неопр.). Онлайн Энциклопедия Целочисленных Последовательностей. OEIS Foundation.

[2] D. C. Gijswijt. A Slow-Growing Sequence Defined by an Unusual Recurrence (неопр.). arXiv.org (2006).

[3] Neil Sloane. Seven Staggering Sequences (неопр.) 3.