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

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

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

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

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

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

${\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 Гофстедтера визначено так:

${\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 Гофстедтера визначено так:

${\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) послідовності Гофстедтера визначено так:

${\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 Гофстедтера визначено так:

${\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-числами». Таким чином, 6-е число Q дорівнює 4. Подання послідовності Q у книзі Гофстедтера, фактично, є першою згадкою мета-послідовностей Фібоначчі в літературі.Тоді як числа Фібоначчі визначають підсумовуванням двох попередніх членів, попередні два члени послідовності Q визначають, наскільки потрібно відсунутись назад, щоб узяти члени послідовності для підсумовування. Індекси для підсумовування визначає та сама послідовність Q.

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

Хоча послідовність Q виглядає хаотичною, подібно до багатьох інших мета-послідовностей Фібоначчі, її члени можна згрупувати в блоки. k-ий блок послідовності Q має 2^k членів. Більш того, для g, що належить блоку, якому належить Q-число, два члени, що використовуються для обчислення Q-числа, звані батьками, переважно містяться в блоці g − 1 і лише кілька членів містяться в блоці g − 2, але ніколи в раніших блоках.

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

Приклад для розуміння алгоритму: наприклад, треба підставляти значення 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.

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

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

${\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), послідовність V з (r,s) = (1,4) і послідовність W з (r, s) = (2,4). Тільки для послідовності V, яка поводиться не настільки хаотично, як дві інші, доведено, що вона не «вмирає». Подібно до початкової послідовності Q, нічого строго не доведено для послідовності W.

Декілька перших членів послідовності 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.

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

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

Сімейство послідовностей Пінна 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, які зсувають індекси сумованих членів уліво (тобто ближче до початку послідовності).

Тільки послідовності F з (i,j) = (0,0), (0,1), (1,0) і (1,1), перша з яких є початковою послідовністю Q, виявляються цілком визначеними. На відміну від 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-доларова послідовність Гофстедтера — Конвея

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

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

${\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, отримав Коллін Маллоуз. У приватній бесіді з Клаусом Пінном Гофстедтер пізніше стверджував, що він знайшов послідовність і її структуру десь за 10-15 років до оголошення Конвеєм премії.

Примітки

1. Hofstadter, 1980, с. 73.
2. Weisstein, Eric W. Hofstadter Figure-Figure Sequence(англ.) на сайті Wolfram MathWorld.
3. Hofstadter, 1980, с. 137.
4. Weisstein, Eric W. Hofstadter G-Sequence(англ.) на сайті Wolfram MathWorld.
5. Weisstein, Eric W. Hofstadter H-Sequence(англ.) на сайті Wolfram MathWorld.
6. Weisstein, Eric W. Hofstadter Male-Female Sequences(англ.) на сайті Wolfram MathWorld.
7. Weisstein, Eric W. Hofstadter's Q-Sequence(англ.) на сайті Wolfram MathWorld.
8. Emerson, 2006, с. 1, 7.
9. Pinn, 1999, с. 5–6.
10. Pinn, 1999, с. 3.
11. Pinn, 2000, с. 1.
12. Emerson, 2006, с. 7.
13. Pinn, 1999, с. 3–4.
14. Balamohan, Kuznetsov, Tanny, 2007, с. 19.
15. Pinn, 1999, с. Abstract, 8.
16. Pinn, 1999, с. 4–5.
17. Pinn, 1999, с. 2.
18. Pinn, 2000, с. 3.
19. Balamohan, Kuznetsov, Tanny, 2007, с. 2.
20. Balamohan, Kuznetsov, Tanny, 2007.
21. Pinn, 2000, с. 16.
22. Weisstein, Eric W. Hofstadter-Conway $10,000 Sequence(англ.) на сайті Wolfram MathWorld.
23. Tempel.

Література

• Michael Tempel. Easy as 1 1 2 2 3 (PDF).
• B. Balamohan, A. Kuznetsov, Stephan M. Tanny. On the Behaviour of a Variant of Hofstadter's Q-Sequence. — Journal of Integer Sequences. — Waterloo, Ontario (Canada) : University of Waterloo, 2007. — Т. 10.
• Nathaniel D. Emerson. [1530-7638 A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions]. — Journal of Integer Sequences. — Waterloo, Ontario (Canada) : University of Waterloo, 2006. — Т. 9.
• Douglas Hofstadter. Gödel, Escher, Bach: an Eternal Golden Braid. — Penguin Books, 1980. — .
• Klaus Pinn. Order and Chaos in Hofstadter's Q(n) Sequence // Complexity. — 1999. — Т. 4, вип. 3. — С. 41–46. — arXiv:chao-dyn/9803012v2. — DOI:10.1002/(SICI)1099-0526(199901/02)4:3<41::AID-CPLX8>3.0.CO;2-3.
• Klaus Pinn. A Chaotic Cousin of Conway's Recursive Sequence // . — 2000. — Т. 9, вип. 1. — С. 55–66. — arXiv:cond-mat/9808031.