Послідовність Гофстедтера — одна з послідовностей зі сімейства цілочисельних послідовностей, визначених нелінійними рекурентними формулами.
Послідовності з книги Гедель, Ешер, Бах: ця нескінченна гірлянда Перші послідовності Гофстедтера описав Дуглас Гофстедтер у своїй книзі Гедель, Ешер, Бах. Послідовності показано в порядку їх подання в розділі III на фігурах і тлі (послідовність Фігура-Фігура) та в розділі V на рекурсивних структурах та процесах (решта послідовностей).
Послідовності Фігура-Фігура Гофстедтера Послідовності Фігура-Фігура Гофстедтера (R і S) — це пара . Послідовність {R} визначено так:
а послідовність {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, … (): S: 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, … ()
Послідовність G Гофстедтера Послідовність G Гофстедтера визначено так:
Декілька перших членів цієї послідовності:
0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, … ()
Послідовність H Гофстедтера Послідовність H Гофстедтера визначено так:
Декілька перших членів цієї послідовності
0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14, … ()
Жіночі та чоловічі послідовності Гофстедтера Жіночі (F) і чоловічі (M) послідовності Гофстедтера визначено так:
Декілька перших членів цих послідовностей:
F: 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13, … (): M: 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, … ()
Послідовність Q Гофстедтера Послідовність Q Гофстедтера визначено так:
Кілька перших членів цієї послідовності:
1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, … ()Гофстедтер назвав члени послідовності «Q-числами». Таким чином, 6-е число Q дорівнює 4. Подання послідовності Q у книзі Гофстедтера, фактично, є першою згадкою мета-послідовностей Фібоначчі в літературі.Тоді як числа Фібоначчі визначають підсумовуванням двох попередніх членів, попередні два члени послідовності Q визначають, наскільки потрібно відсунутись назад, щоб узяти члени послідовності для підсумовування. Індекси для підсумовування визначає та сама послідовність Q.
Q(1), перший елемент послідовності, використовують тільки для обчислення Q(3).
Хоча послідовність Q виглядає хаотичною, подібно до багатьох інших мета-послідовностей Фібоначчі, її члени можна згрупувати в блоки. k-ий блок послідовності Q має 2k членів. Більш того, для 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 послідовності
Сімейство Гофстедтера — Губера Qr,s(n) За 20 років після того, як Гофстедтер описав послідовність Q, Гофстедтер і Грег Губер використали символ Q для узагальнення послідовності Q до сімейства послідовностей, а початкову послідовність Q перейменували на послідовність U.
Початкова послідовність Q узагальнюється заміною (n − 1) і (n − 2) на (n − r) та (n − s) відповідно.
Це породило сімейство послідовностей
де s ≥ 2 та r < s.
При (r,s) = (1,2) отримуємо оригінальну послідовність Q, так що вона є членом цього сімейства. Нині відомі тільки три послідовності сімейства Qr,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, … ()
Декілька перших членів послідовності W:
1, 1, 1, 1, 2, 4, 6, 7, 7, 5, 3, 8, 9, 11, 12, 9, 9, 13, 11, 9, … ()
Для інших значень (r,s) послідовності рано чи пізно «вмирають», тобто, існує n для якого значення Qr,s (n) не визначене, оскільки n − Qr,s (n − r) < 1.
Сімейство послідовностей Fi,j(n) 1998 року Клаус Пінн, науковець із Мюнстерського університету (Німеччина) за тісного контакту з Гофстедтером, запропонував інше узагальнення послідовності Q Гофстедтера, і назвав отримані послідовності F-послідовностями.
Сімейство послідовностей Пінна Fi,j визначають так:
Таким чином, Пінн увів додаткові сталі i та j, які зсувають індекси сумованих членів уліво (тобто ближче до початку послідовності).
Тільки послідовності F з (i,j) = (0,0), (0,1), (1,0) і (1,1), перша з яких є початковою послідовністю Q, виявляються цілком визначеними. На відміну від 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, …
10000-доларова послідовність Гофстедтера — Конвея
10000-доларова послідовність Гофстедтера — Конвея визначають так:
Перші кілька членів послідовності:
1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, … ()
Послідовність отримала таку назву через те, що Джон Конвей оголосив про премію $10000 будь-кому, хто продемонструє певний результат про асимптотичну поведінку послідовності. Премію, що зменшилася до $1000, отримав Коллін Маллоуз. У приватній бесіді з Клаусом Пінном Гофстедтер пізніше стверджував, що він знайшов послідовність і її структуру десь за 10-15 років до оголошення Конвеєм премії.
Примітки
Література