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

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

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

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

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

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

{\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]:

{\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]:

{\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]:

{\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]:

{\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].

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

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 визначають так:

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-доларова послідовність Гофстедтера — Конвея ред.

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

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

{\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].

Примітки ред.

↑ Hofstadter, 1980, с. 73.
↑ Weisstein, Eric W. Hofstadter Figure-Figure Sequence(англ.) на сайті Wolfram MathWorld.
↑ ^а ^б ^в ^г ^д ^е Hofstadter, 1980, с. 137.
↑ Weisstein, Eric W. Hofstadter G-Sequence(англ.) на сайті Wolfram MathWorld.
↑ Weisstein, Eric W. Hofstadter H-Sequence(англ.) на сайті Wolfram MathWorld.
↑ Weisstein, Eric W. Hofstadter Male-Female Sequences(англ.) на сайті Wolfram MathWorld.
↑ Weisstein, Eric W. Hofstadter's Q-Sequence(англ.) на сайті Wolfram MathWorld.
↑ Emerson, 2006, с. 1, 7.
↑ Pinn, 1999, с. 5–6.
↑ ^а ^б Pinn, 1999, с. 3.
↑ Pinn, 2000, с. 1.
↑ ^а ^б Emerson, 2006, с. 7.
↑ Pinn, 1999, с. 3–4.
↑ Balamohan, Kuznetsov, Tanny, 2007, с. 19.
↑ Pinn, 1999, с. Abstract, 8.
↑ Pinn, 1999, с. 4–5.
↑ ^а ^б Pinn, 1999, с. 2.
↑ Pinn, 2000, с. 3.
↑ ^а ^б ^в ^г ^д ^е ^ж ^и ^к Balamohan, Kuznetsov, Tanny, 2007, с. 2.
↑ Balamohan, Kuznetsov, Tanny, 2007.
↑ ^а ^б ^в Pinn, 2000, с. 16.
↑ Weisstein, Eric W. Hofstadter-Conway $10,000 Sequence(англ.) на сайті Wolfram MathWorld.
↑ 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. — ISBN 0-14-005579-7.
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 // Experimental Mathematics. — 2000. — Т. 9, вип. 1. — С. 55–66. — arXiv:cond-mat/9808031.

[FOOTNOTEHofstadter198073-1] Hofstadter, 1980, с. 73.

[2] Weisstein, Eric W. Hofstadter Figure-Figure Sequence(англ.) на сайті Wolfram MathWorld.

[FOOTNOTEHofstadter1980137-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.

[FOOTNOTEEmerson20061,_7-8] Emerson, 2006, с. 1, 7.

[FOOTNOTEPinn19995–6-9] Pinn, 1999, с. 5–6.

[FOOTNOTEPinn19993-10] а ^б Pinn, 1999, с. 3.

[FOOTNOTEPinn20001-11] Pinn, 2000, с. 1.

[FOOTNOTEEmerson20067-12] а ^б Emerson, 2006, с. 7.

[FOOTNOTEPinn19993–4-13] Pinn, 1999, с. 3–4.

[FOOTNOTEBalamohan,_Kuznetsov,_Tanny200719-14] Balamohan, Kuznetsov, Tanny, 2007, с. 19.

[FOOTNOTEPinn1999Abstract,_8-15] Pinn, 1999, с. Abstract, 8.

[FOOTNOTEPinn19994–5-16] Pinn, 1999, с. 4–5.

[FOOTNOTEPinn19992-17] а ^б Pinn, 1999, с. 2.

[FOOTNOTEPinn20003-18] Pinn, 2000, с. 3.

[FOOTNOTEBalamohan,_Kuznetsov,_Tanny20072-19] а ^б ^в ^г ^д ^е ^ж ^и ^к Balamohan, Kuznetsov, Tanny, 2007, с. 2.

[FOOTNOTEBalamohan,_Kuznetsov,_Tanny2007-20] Balamohan, Kuznetsov, Tanny, 2007.

[FOOTNOTEPinn200016-21] а ^б ^в Pinn, 2000, с. 16.

[22] Weisstein, Eric W. Hofstadter-Conway $10,000 Sequence(англ.) на сайті Wolfram MathWorld.

[FOOTNOTETempel-23] Tempel.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]