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

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

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

[ред. | ред. код]

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

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

[ред. | ред. код]

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

а послідовність {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]:

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

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

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

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

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

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

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

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 має 2k членів[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 послідовності

[ред. | ред. код]

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

[ред. | ред. код]

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

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

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

де s ≥ 2 та r < s.

При (r,s) = (1,2) отримуємо оригінальну послідовність Q, так що вона є членом цього сімейства. Нині відомі тільки три послідовності сімейства Qr,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].

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

[ред. | ред. код]

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

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

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

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

Перші кілька членів послідовності F0,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]:

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

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

Примітки

[ред. | ред. код]
  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. — 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.