Послідовність Гофстедтера

Послідовність Гофстедтера — одна з послідовностей зі сімейства цілочисельних послідовностей, визначених нелінійними рекурентними формулами.

Послідовності з книги Гедель, Ешер, Бах: ця нескінченна гірлянда

Перші послідовності Гофстедтера описав Дуглас Гофстедтер у своїй книзі Гедель, Ешер, Бах. Послідовності показано в порядку їх подання в розділі III на фігурах і тлі (послідовність Фігура-Фігура) та в розділі V на рекурсивних структурах та процесах (решта послідовностей).

Послідовності Фігура-Фігура Гофстедтера

Послідовності Фігура-Фігура Гофстедтера (R і S) — це пара комплементарних цілочисельних послідовностей^[en]. Послідовність {R} визначено так^[1][2]:

${\displaystyle {\begin{aligned}R(1)&=1~;\ S(1)=2\\R(n)&=R(n-1)+S(n-1),\quad n>1.\end{aligned}}}$

а послідовність {S(n)} визначено як строго зростальна послідовність додатних цілих чисел, відсутніх у {R(n)}. Перші кілька членів цих послідовностей: R: 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236, 260, … (послідовність A005228 з Онлайн енциклопедії послідовностей цілих чисел, OEIS): S: 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, … (послідовність A030124 з Онлайн енциклопедії послідовностей цілих чисел, OEIS)

Послідовність G Гофстедтера

Послідовність G Гофстедтера визначено так^[3][4]:

${\displaystyle {\begin{aligned}G(0)&=0\\G(n)&=n-G(G(n-1)),\quad n>0.\end{aligned}}}$

Декілька перших членів цієї послідовності:

0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, … (послідовність A005206 з Онлайн енциклопедії послідовностей цілих чисел, OEIS)

Послідовність H Гофстедтера

Послідовність H Гофстедтера визначено так^[3][5]:

${\displaystyle {\begin{aligned}H(0)&=0\\H(n)&=n-H(H(H(n-1))),\quad n>0.\end{aligned}}}$

Декілька перших членів цієї послідовності

0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14, … (послідовність A005374 з Онлайн енциклопедії послідовностей цілих чисел, OEIS)

Жіночі та чоловічі послідовності Гофстедтера

Жіночі (F) і чоловічі (M) послідовності Гофстедтера визначено так^[3][6]:

${\displaystyle {\begin{aligned}F(0)&=1~;\ M(0)=0\\M(n)&=n-F(M(n-1)),\quad n>0\\F(n)&=n-M(F(n-1)),\quad n>0.\end{aligned}}}$

Декілька перших членів цих послідовностей:

F: 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13, … (послідовність A005378 з Онлайн енциклопедії послідовностей цілих чисел, OEIS): M: 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, … (послідовність A005379 з Онлайн енциклопедії послідовностей цілих чисел, OEIS)

Послідовність Q Гофстедтера

Послідовність Q Гофстедтера визначено так^[3][7]:

${\displaystyle {\begin{aligned}Q(1)&=Q(2)=1,\\Q(n)&=Q(n-Q(n-1))+Q(n-Q(n-2)),\quad n>2.\end{aligned}}}$

Кілька перших членів цієї послідовності:

1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, … (послідовність A005185 з Онлайн енциклопедії послідовностей цілих чисел, OEIS)Гофстедтер назвав члени послідовності «Q-числами»^[3]. Таким чином, 6-е число Q дорівнює 4. Подання послідовності Q у книзі Гофстедтера, фактично, є першою згадкою мета-послідовностей Фібоначчі в літературі^[8].Тоді як числа Фібоначчі визначають підсумовуванням двох попередніх членів, попередні два члени послідовності Q визначають, наскільки потрібно відсунутись назад, щоб узяти члени послідовності для підсумовування. Індекси для підсумовування визначає та сама послідовність Q.

Q(1), перший елемент послідовності, використовують тільки для обчислення Q(3)^[9].

Хоча послідовність Q виглядає хаотичною^{[3][10][11][12]}, подібно до багатьох інших мета-послідовностей Фібоначчі, її члени можна згрупувати в блоки^[13][14]. k-ий блок послідовності Q має 2^k членів^[15]. Більш того, для g, що належить блоку, якому належить Q-число, два члени, що використовуються для обчислення Q-числа, звані батьками, переважно містяться в блоці g − 1 і лише кілька членів містяться в блоці g − 2, але ніколи в раніших блоках^[16].

Більшість таких знахідок є емпіричними спостереженнями, оскільки наразі про послідовність Q нічого строго не доведено^[17][18][19]. Зокрема, невідомо, чи є послідовність цілком визначеною для всіх n. Тобто, чи не «вмирає» послідовність у деякій точці, намагаючись використати член послідовності зліва від першого члена Q(1)^[12][17][19].

Приклад для розуміння алгоритму: наприклад, треба підставляти значення Q(1) = 1, Q(2)=1 (за умовою).

Q(3) = Q(3-1)+Q(3-1) = Q(2)+ Q(2) = 2

Q(4) = (Q(4-Q(3))+Q(4-Q(2)) = Q(4-2)+Q(4-1) = Q(2)+Q(3) = 1+2=3

Узагальнення Q послідовності

Сімейство Гофстедтера — Губера Q_r,s(n)

За 20 років після того, як Гофстедтер описав послідовність Q, Гофстедтер і Грег Губер використали символ Q для узагальнення послідовності Q до сімейства послідовностей, а початкову послідовність Q перейменували на послідовність U^[19].

Початкова послідовність Q узагальнюється заміною (n − 1) і (n − 2) на (n − r) та (n − s) відповідно^[19].

Це породило сімейство послідовностей

${\displaystyle Q_{r,s}(n)={\begin{cases}1,\quad 1\leq n\leq s,\\Q_{r,s}(n-Q_{r,s}(n-r))+Q_{r,s}(n-Q_{r,s}(n-s)),\quad n>s,\end{cases}}}$

де s ≥ 2 та r < s.

При (r,s) = (1,2) отримуємо оригінальну послідовність Q, так що вона є членом цього сімейства. Нині відомі тільки три послідовності сімейства Q_r,s, а саме, послідовність U з (r,s) = (1,2) (оригінальна послідовність Q)^[19], послідовність V з (r,s) = (1,4)^[20] і послідовність W з (r, s) = (2,4)^[19]. Тільки для послідовності V, яка поводиться не настільки хаотично, як дві інші, доведено, що вона не «вмирає»^[19]. Подібно до початкової послідовності Q, нічого строго не доведено для послідовності W^[19].

Декілька перших членів послідовності V:

1, 1, 1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 11, … (послідовність A063882 з Онлайн енциклопедії послідовностей цілих чисел, OEIS)

Декілька перших членів послідовності W:

1, 1, 1, 1, 2, 4, 6, 7, 7, 5, 3, 8, 9, 11, 12, 9, 9, 13, 11, 9, … (послідовність A087777 з Онлайн енциклопедії послідовностей цілих чисел, OEIS)

Для інших значень (r,s) послідовності рано чи пізно «вмирають», тобто, існує n для якого значення Qr,s (n) не визначене, оскільки n − Qr,s (n − r) < 1^[19].

Сімейство послідовностей F_i,j(n)

1998 року Клаус Пінн, науковець із Мюнстерського університету (Німеччина) за тісного контакту з Гофстедтером, запропонував інше узагальнення послідовності Q Гофстедтера, і назвав отримані послідовності F-послідовностями^[21].

Сімейство послідовностей Пінна F_i,j визначають так:

${\displaystyle F_{i,j}(n)={\begin{cases}1,\quad n=1,2,\\F_{i,j}(n-i-F_{i,j}(n-1))+F_{i,j}(n-j-F_{i,j}(n-2)),\quad n>2.\end{cases}}}$

Таким чином, Пінн увів додаткові сталі i та j, які зсувають індекси сумованих членів уліво (тобто ближче до початку послідовності)^[21].

Тільки послідовності F з (i,j) = (0,0), (0,1), (1,0) і (1,1), перша з яких є початковою послідовністю Q, виявляються цілком визначеними^[21]. На відміну від Q(1), перші елементи послідовностей Пінна F_i,j(n) використовуються для обчислення інших елементів у послідовності, якщо одна з додаткових сталих дорівнює 1.

Перші кілька членів послідовності F_0,1 Пінна:

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 9, 10, 10, 11, … послідовність A046699 з Онлайн енциклопедії послідовностей цілих чисел, OEIS

10000-доларова послідовність Гофстедтера&nbsp;— Конвея

Конвей довів, що графік функції a(n)/n прямує до 0,5

10000-доларова послідовність Гофстедтера — Конвея визначають так^[22]:

${\displaystyle {\begin{aligned}a(1)&=a(2)=1,\\a(n)&=a(a(n-1))+a(n-a(n-1)),\quad n>2.\end{aligned}}}$

Перші кілька членів послідовності:

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, … (послідовність A004001 з Онлайн енциклопедії послідовностей цілих чисел, OEIS)

Послідовність отримала таку назву через те, що Джон Конвей оголосив про премію $10000 будь-кому, хто продемонструє певний результат про асимптотичну поведінку послідовності. Премію, що зменшилася до $1000, отримав Коллін Маллоуз^[23]. У приватній бесіді з Клаусом Пінном Гофстедтер пізніше стверджував, що він знайшов послідовність і її структуру десь за 10-15 років до оголошення Конвеєм премії^[10].