Русская Википедия:Последовательность Хофштадтера
Последовательность Хофштадтера — это одна из последовательностей из семейства целочисленных последовательностей, определённых нелинейными рекуррентными формулами.
Последовательности из книги Гёдель, Эшер, Бах: эта бесконечная гирлянда
Первые последовательности Хофштадтера описал Дуглас Хофштадтер в своей книге Гёдель, Эшер, Бах. Последовательности показаны в порядке их представления в главе III на фигурах и фоне (последовательность Фигура-Фигура) и в главе V на рекурсивных структурах и процессах (остальные последовательности).
Последовательности Рисунок-Рисунок Хофштадтера
Последовательности Рисунок-Рисунок Хофштадтера (R и S) — это пара Шаблон:Не переведено 5. Последовательность {R} определяется следующим образомШаблон:Sfn[1]
- <math>
\begin{align} R(1)&=1~ ;\ S(1)=2 \\ R(n)&=R(n-1)+S(n-1), \quad n>1. \end{align} </math>
а последовательность {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[2]
- <math>
\begin{align} G(0)&=0 \\ G(n)&=n-G(G(n-1)), \quad n>0. \end{align} </math>
Несколько первых членов этой последовательности
- 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[3]
- <math>
\begin{align} H(0)&=0 \\ H(n)&=n-H(H(H(n-1))), \quad n>0. \end{align} </math>
Несколько первых членов этой последовательности
- 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[4]
- <math>
\begin{align} 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{align} </math>
Несколько первых членов этих последовательностей
- 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[5]:
- <math>
\begin{align} Q(1)&=Q(2)=1, \\ Q(n)&=Q(n-Q(n-1))+Q(n-Q(n-2)), \quad n>2. \end{align} </math>
Несколько первых членов этой последовательности
- 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. Для последовательности Q k-ый блок имеет 2k членовШаблон: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 последовательности
Семейство Хофштадтера–Хубера Qr,s(n)
20 лет спустя после описания Хофштадтером последовательности Q, Хофштадтер и Грег Хубер использовали символ Q для обобщения последовательности Q до семейства последовательностей, а исходную последовательность Q переименовали в последовательность U Шаблон:Sfn.
Исходная последовательность Q обобщается путём замены (n − 1) и (n − 2) на (n − r) и (n − s) соответственноШаблон:Sfn.
Это привело к семейству последовательностей
- <math>
Q_{r,s}(n) = \begin{cases} 1 , \quad 1 \le n \le s, \\ Q_{r,s}(n-Q_{r,s}(n-r))+Q_{r,s}(n-Q_{r,s}(n-s)), \quad n > s, \end{cases} </math>
где s ≥ 2 и r < s.
При (r,s) = (1,2) получаем оригинальную последовательность Q, так что она является членом этого семейства. В настоящее время известны только три последовательности семейства Qr,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.
Семейство последовательностей Fi,j(n)
В 1998 Клаус Пинн, учёный из Мюнстерского университета (Германия) при тесном контакте с Хофштадтером, предложил другое обобщение последовательности Q Хофштадтера, и назвал полученные последовательности F-последовательностямиШаблон:Sfn.
Семейство последовательностей Пинна Fi,j определяется следующим образом:
- <math>
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} </math>
Таким образом, Пинн ввёл дополнительные константы i и j, которые сдвигают индексы суммируемых членов влево (то есть ближе к началу последовательности)Шаблон:Sfn.
Только последовательности F с (i,j) = (0,0), (0,1), (1,0) и (1,1), первая из которых является исходной последовательностью Q, оказываются вполне определённымиШаблон:Sfn. В отличие от 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, ... Шаблон:OEIS
10000-долларовая последовательность Хофштадтера — Конвея
10000-долларовая последовательность Хофштадтера-Конвея определяется следующим образом[6]
- <math>
\begin{align} a(1)&=a(2)=1, \\ a(n)&=a(a(n-1))+a(n-a(n-1)), \quad n>2. \end{align} </math>
Первые несколько членов последовательности
- 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.
Примечания
Литература
