Последовательность Хофштадтера

Последовательность Хофштадтера — это одна из последовательностей из семейства целочисленных последовательностей, определённых нелинейными рекуррентными формулами.

Последовательности из книги Гёдель, Эшер, Бах: эта бесконечная гирлянда

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

Последовательности Рисунок-Рисунок Хофштадтера

Последовательности Рисунок-Рисунок Хофштадтера (R и S) — это пара комплементарных целочисленных последовательностей. Последовательность {R} определяется следующим образом

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

а последовательность {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 Хофштадтера определяется следующим образом

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

Несколько первых членов этой последовательности

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 Хофштадтера определяется следующим образом

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

Несколько первых членов этой последовательности

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) последовательности Хофштадтера определяются следующим образом

${\begin{aligned}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{aligned}}$

Несколько первых членов этих последовательностей

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 Хофштадтера определяется следующим образом:

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

Несколько первых членов этой последовательности

1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, ... (последовательность A005185 в OEIS)

Хофштадтер назвал члены последовательности «Q-числами» . Таким образом 6-ое число Q равно 4. Представление последовательности Q в книге Хофштадтера, фактически, является первым упоминанием мета-последовательностей Фибоначчи в литературе.

В то время как числа Фибоначчи определяются суммированием двух предыдущих членов, предыдущие два члена последовательности Q определяют, насколько нужно отодвинуться назад, чтобы взять члены последовательности для суммирования. Индексы для суммирования задаются той же последовательностью Q.

Q(1), первый элемент последовательности, используется только для вычисления Q(3) .

Хотя последовательность Q выглядит хаотической, подобно многим другим мета-последовательностям Фибоначчи, её члены можно сгруппировать в блоки. Для последовательности Q k-ый блок имеет 2^k членов. Более того, для 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 последовательности

Семейство Хофштадтера–Хубера Q_r,s(n)

20 лет спустя после описания Хофштадтером последовательности Q, Хофштадтер и Грег Хубер использовали символ Q для обобщения последовательности Q до семейства последовательностей, а исходную последовательность Q переименовали в последовательность U .

Исходная последовательность Q обобщается путём замены (n − 1) и (n − 2) на (n − r) и (n − s) соответственно.

Это привело к семейству последовательностей

$Q_{r,s}(n)={\begin{cases}1,\quad 1\leq n\leq s,\\Q_{r,s}(n-Q_{r,s}(n-r))+Q_{r,s}(n-Q_{r,s}(n-s)),\quad n>s,\end{cases}}$

где s ≥ 2 и r < s.

При (r,s) = (1,2) получаем оригинальную последовательность Q, так что она является членом этого семейства. В настоящее время известны только три последовательности семейства Q_r,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, ... (последовательность 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.

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

В 1998 Клаус Пинн, учёный из Мюнстерского университета (Германия) при тесном контакте с Хофштадтером, предложил другое обобщение последовательности Q Хофштадтера, и назвал полученные последовательности F-последовательностями.

Семейство последовательностей Пинна F_i,j определяется следующим образом:

$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}}$

Таким образом, Пинн ввёл дополнительные константы i и j, которые сдвигают индексы суммируемых членов влево (то есть ближе к началу последовательности).

Только последовательности F с (i,j) = (0,0), (0,1), (1,0) и (1,1), первая из которых является исходной последовательностью Q, оказываются вполне определёнными. В отличие от 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, ... последовательность A046699 в OEIS

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

График функции a(n)/n стремится к 0,5, как доказал Конвей

10000-долларовая последовательность Хофштадтера-Конвея определяется следующим образом

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

Первые несколько членов последовательности

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, … (последовательность A004001 в OEIS)

Последовательность получила такое название из-за того, что Джон Хортон Конвей объявил о премии в $10000 любому, кто продемонстрирует определённый результат об асимптотическом поведении последовательности. Премию, уменьшившуюся до $1000, получил Коллин Маллоуз. В частной беседе с Клаусом Пинном Хофштадтер позднее утверждал, что он нашёл последовательность и её структуру где-то за 10-15 лет до объявления Конвеем премии.