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

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

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

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

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

${\displaystyle {\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 Хофштадтера определяется следующим образом ^[3][4]

${\displaystyle {\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 Хофштадтера определяется следующим образом ^[3][5]

${\displaystyle {\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) последователи Хофштадтера определяется следующим образом ^[3][6]

${\displaystyle {\begin{aligned}F(0)&=1~;\ M(0)=0\\F(n)&=n-M(F(n-1)),\quad n>0\\M(n)&=n-F(M(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 Хофштадтера определяется следующим образом ^[3][7]

${\displaystyle {\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-числами» ^[3]. Таким образом 6-ое число Q равно 4. Представление последовательности Q в книге Хофштадтера, фактически, является первым упоминанием мета-последовательностей Фибоначчи в литературе ^[8].

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

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

Хотя последовательность Q выглядят хаотической ^{[3][10][11][12]}, подобно многим другим мета-последовательностям Фибоначчи, её члены можно сгруппировать в блоки ^[13][14]. Для последовательности Q k-ый блок имеет 2^k членов ^[15]. Более того, для g, принадлежащему блоку, которому принадлежит Q-число, два члена, используемые для вычисления Q-числа, называемые родителями, большей частью находятся в блоке g − 1 и только несколько членов находятся в блоке g − 2, но никогда в более ранних блоках ^[16].

Большинство из таких находок являются эмпирическими наблюдениями, поскольку ничего до настоящего времени не было доказано строго о последовательности Q ^[17][18][19]. В частности, неизвестно, является последовательность вполне определённой для всех n. То есть, не «умирает» ли последовательность в некоторой точке, пытаясь использовать член последовательности слева от первого члена Q(1). ^[12][17][19]

Обобщения Q последовательности

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

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

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

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

${\displaystyle 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) ^[19], последовательность V с (r,s) = (1,4) ^[20] и последовательность W с (r,s) = (2,4) ^[19]. Только для последовательности V, которая не ведёт себя столь хаотически, как две другие, доказано, что она не «умирает» ^[19]. Подобно исходной последовательности Q, ничего не было доказано строго для последовательности W ^[19].

Несколько первых членов последовательности 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, для которого значение Q_r,s(n) не определено, поскольку n − Q_r,s(n − r) < 1 ^[19].

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

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

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

${\displaystyle 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, которые сдвигают индексы суммируемых членов влево (то есть, ближе к началу последовательности) ^[21].

Только последовательности F с (i,j) = (0,0), (0,1), (1,0) и (1,1), первая из которых является исходной последовательностью Q, оказываются вполне определёнными ^[21]. В отличие от Q(1), первые элементы последовательностей Пинна F_i,j(n) используются для вычисления других элементов в последовательности, если одна из дополнительных констант равна 1.

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

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

Последовательность $10,000 Хофштадтера–Конвея

Последовательность $10,000 Хофштадтера–Конвея определяется следующим образом ^[22]

${\displaystyle {\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 любому, кто продемонстрирует какой-либо результат об асимптотическом^[en] поведении последовательности. Премию, уменьшившуюся до $1,000, получил Коллин Маллоуз ^[23]. В частной беседе с Клаусом Пинном Хофштадтер позднее утверждал, что он нашёл последовательность и её структуру где-то за 10–15 лет до объявления Конвеем премии ^[10].

Примечания