Послідовність Гофстедтера — одна з послідовностей зі сімейства цілочисельних послідовностей, визначених нелінійними рекурентними формулами.
Перші послідовності Гофстедтера описав Дуглас Гофстедтер у своїй книзі Гедель, Ешер, Бах. Послідовності показано в порядку їх подання в розділі 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 Гофстедтера визначено так[3][4]:
Декілька перших членів цієї послідовності:
Послідовність H Гофстедтера визначено так[3][5]:
Декілька перших членів цієї послідовності
Жіночі (F) і чоловічі (M) послідовності Гофстедтера визначено так[3][6]:
Декілька перших членів цих послідовностей:
Послідовність Q Гофстедтера визначено так[3][7]:
Кілька перших членів цієї послідовності:
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
За 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:
Декілька перших членів послідовності W:
Для інших значень (r,s) послідовності рано чи пізно «вмирають», тобто, існує n для якого значення Qr,s (n) не визначене, оскільки n − Qr,s (n − r) < 1[19].
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 Пінна:
10000-доларова послідовність Гофстедтера — Конвея визначають так[22]:
Перші кілька членів послідовності:
Послідовність отримала таку назву через те, що Джон Конвей оголосив про премію $10000 будь-кому, хто продемонструє певний результат про асимптотичну поведінку послідовності. Премію, що зменшилася до $1000, отримав Коллін Маллоуз[23]. У приватній бесіді з Клаусом Пінном Гофстедтер пізніше стверджував, що він знайшов послідовність і її структуру десь за 10-15 років до оголошення Конвеєм премії[10].