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

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

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

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

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

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

$\begin{array}{cc}R(1)& =1;S(1)=2\\ R(n)& =R(n-1)+S(n-1),n>1.\end{array}$

а послідовність {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, … (Шаблон:OEIS): S: 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, … (Шаблон:OEIS)

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

Послідовність G Гофстедтера визначено такШаблон:Sfn:

$\begin{array}{cc}G(0)& =0\\ G(n)& =n-G(G(n-1)),n>0.\end{array}$

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

0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, … (Шаблон:OEIS)

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

Послідовність H Гофстедтера визначено такШаблон:Sfn:

$\begin{array}{cc}H(0)& =0\\ H(n)& =n-H(H(H(n-1))),n>0.\end{array}$

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

0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14, … (Шаблон:OEIS)

Жіночі та чоловічі послідовності Гофстедтера

Жіночі (F) і чоловічі (M) послідовності Гофстедтера визначено такШаблон:Sfn:

$\begin{array}{cc}F(0)& =1;M(0)=0\\ M(n)& =n-F(M(n-1)),n>0\\ F(n)& =n-M(F(n-1)),n>0.\end{array}$

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

F: 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13, … (Шаблон:OEIS): M: 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, … (Шаблон:OEIS)

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

Послідовність Q Гофстедтера визначено такШаблон:Sfn:

$\begin{array}{cc}Q(1)& =Q(2)=1,\\ Q(n)& =Q(n-Q(n-1))+Q(n-Q(n-2)),n>2.\end{array}$

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

1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, … (Шаблон:OEIS)Гофстедтер назвав члени послідовності «Q-числами»Шаблон:Sfn. Таким чином, 6-е число Q дорівнює 4. Подання послідовності Q у книзі Гофстедтера, фактично, є першою згадкою мета-послідовностей Фібоначчі в літературіШаблон:Sfn.Тоді як числа Фібоначчі визначають підсумовуванням двох попередніх членів, попередні два члени послідовності Q визначають, наскільки потрібно відсунутись назад, щоб узяти члени послідовності для підсумовування. Індекси для підсумовування визначає та сама послідовність Q.

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

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

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

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

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

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

$Q_{r,s}(n)=\{\begin{array}{c}1,1\le n\le s,\\ Q_{r,s}(n-Q_{r,s}(n-r))+Q_{r,s}(n-Q_{r,s}(n-s)),n>s,\end{array}$

де s ≥ 2 та r < s.

При (r,s) = (1,2) отримуємо оригінальну послідовність Q, так що вона є членом цього сімейства. Нині відомі тільки три послідовності сімейства Q_r,s, а саме, послідовність U з (r,s) = (1,2) (оригінальна послідовність Q)Шаблон:Sfn, послідовність V з (r,s) = (1,4)Шаблон:Sfn і послідовність W з (r, s) = (2,4)Шаблон:Sfn. Тільки для послідовності V, яка поводиться не настільки хаотично, як дві інші, доведено, що вона не «вмирає»Шаблон:Sfn. Подібно до початкової послідовності Q, нічого строго не доведено для послідовності WШаблон:Sfn.

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

1, 1, 1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 11, … (Шаблон:OEIS)

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

1, 1, 1, 1, 2, 4, 6, 7, 7, 5, 3, 8, 9, 11, 12, 9, 9, 13, 11, 9, … (Шаблон:OEIS)

Для інших значень (r,s) послідовності рано чи пізно «вмирають», тобто, існує n для якого значення Qr,s (n) не визначене, оскільки n − Qr,s (n − r) < 1Шаблон:Sfn.

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

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

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

$F_{i,j}(n)=\{\begin{array}{c}1,n=1,2,\\ F_{i,j}(n-i-F_{i,j}(n-1))+F_{i,j}(n-j-F_{i,j}(n-2)),n>2.\end{array}$

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

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

10000-доларова послідовність Гофстедтера — Конвея

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

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

$\begin{array}{cc}a(1)& =a(2)=1,\\ a(n)& =a(a(n-1))+a(n-a(n-1)),n>2.\end{array}$

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

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, … (Шаблон:OEIS)

Послідовність отримала таку назву через те, що Джон Конвей оголосив про премію $10000 будь-кому, хто продемонструє певний результат про асимптотичну поведінку послідовності. Премію, що зменшилася до $1000, отримав Коллін МаллоузШаблон:Sfn. У приватній бесіді з Клаусом Пінном Гофстедтер пізніше стверджував, що він знайшов послідовність і її структуру десь за 10-15 років до оголошення Конвеєм преміїШаблон:Sfn.

Література

• Шаблон:Cite web
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття