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

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

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

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

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

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

${\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, ... (последовательность в OEIS )

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

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

${\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, ... (последовательность в OEIS )

Женские и мужские последовательности Хофштадтера

Женские (F) и мужские (M) последовательности Хофштадтера определяются следующим образом

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

${\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, ... (последовательность в 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 ) соответственно .

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

${\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 ) , последовательность 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, ... (последовательность в 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 , для которого значение Q r , s ( n ) не определено, поскольку n − Q r , s ( n − r ) < 1 .

Семейство последовательностей F _{i , j} ( n )

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

Семейство последовательностей Пинна 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 , которые сдвигают индексы суммируемых членов влево (то есть ближе к началу последовательности) .

Только последовательности 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, ... последовательность в OEIS

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

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

${\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, … (последовательность в OEIS )

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

Примечания

Литература