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

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

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


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

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


 Последовательности Рисунок-Рисунок Хофштадтера (R и S) — это пара . Последовательность \{R\} определяется следующим образом
R(1)=1; S(1)=2R(n)=R(n1)+S(n1),n>1.

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

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


 Последовательность G Хофштадтера определяется следующим образом
G(0)=0G(n)=nG(G(n1)),n>0.

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

  0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, ...

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


 Последовательность H Хофштадтера определяется следующим образом
H(0)=0H(n)=nH(H(H(n1))),n>0.

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

  0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14, ...

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


 Женские (F) и мужские (M) последователи Хофштадтера определяются следующим образом
F(0)=1; M(0)=0F(n)=nM(F(n1)),n>0M(n)=nF(M(n1)),n>0.

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

  F: 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13, ...
 M: 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, ...

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


 Последовательность Q Хофштадтера определяется следующим образом:
Q(1)=Q(2)=1,Q(n)=Q(nQ(n1))+Q(nQ(n2)),n>2.

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

  1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, ...
  Хофштадтер назвал члены последовательности «Q-числами» . Таким образом 6-ое число Q равно 4. Представление последовательности Q в книге Хофштадтера, фактически, является первым упоминанием мета-последовательностей Фибоначчи в литературе.
 В то время как числа Фибоначчи определяются суммированием двух предыдущих членов, предыдущие два члена последовательности Q определяют, насколько нужно отодвинуться назад, чтобы взять члены последовательности для суммирования. Индексы для суммирования задаются той же последовательностью Q.
 Q(1), первый элемент последовательности, используется только для вычисления Q(3) .
 Хотя последовательность Q выглядит хаотической, подобно многим другим мета-последовательностям Фибоначчи, её члены можно сгруппировать в блоки. Для последовательности Q k-ый блок имеет 2k членов. Более того, для g, принадлежащему блоку, которому принадлежит Q-число, два члена, используемые для вычисления Q-числа, называемые родителями, большей частью находятся в блоке g − 1 и только несколько членов находятся в блоке g − 2, но никогда в более ранних блоках.
 Большинство из таких находок являются эмпирическими наблюдениями, поскольку ничего до настоящего времени не было доказано строго о последовательности Q. В частности, неизвестно, является последовательность вполне определённой для всех n. То есть не «умирает» ли последовательность в некоторой точке, пытаясь использовать член последовательности слева от первого члена Q(1).

Обобщения Q

последовательности

Семейство Хофштадтера–Хубера Q

\emphr,\emphs(n)
 20 лет спустя после описания Хофштадтером последовательности Q, Хофштадтер и Грег Хубер использовали символ Q для обобщения последовательности Q до семейства последовательностей, а исходную последовательность Q переименовали в последовательность U .
 Исходная последовательность Q обобщается путём замены (n − 1) и (n − 2) на (n − r) и (n − s) соответственно.
 Это привело к семейству последовательностей
Qr,s(n)={1,1ns,Qr,s(nQr,s(nr))+Qr,s(nQr,s(ns)),n>s,

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

  1, 1, 1, 1, 2, 4, 6, 7, 7, 5, 3, 8, 9, 11, 12, 9, 9, 13, 11, 9, ...
  Для других значений (r,s) последовательности рано или поздно «умирают», т.е. существует n, для которого значение Q\emphr,\emphs(n'') не определено, поскольку n − Qr,\emphs(n − r) \textless 1.

Семейство последовательностей F

\emphi,\emphj(n)
 В 1998 Клаус Пинн, учёный из Мюнстерского университета (Германия) при тесном контакте с Хофштадтером, предложил другое обобщение последовательности Q Хофштадтера, и назвал полученные последовательности F-последовательностями.
 Семейство последовательностей Пинна Fi,\emphj определяется следующим образом:
Fi,j(n)={1,n=1,2,Fi,j(niFi,j(n1))+Fi,j(njFi,j(n2)),n>2.

 Таким образом, Пинн ввёл дополнительные константы i и j, которые сдвигают индексы суммируемых членов влево (то есть ближе к началу последовательности).
 Только последовательности F с (i,j) = (0,0), (0,1), (1,0) и (1,1), первая из которых является исходной последовательностью Q, оказываются вполне определёнными. В отличие от Q(1), первые элементы последовательностей Пинна Fi,\emphj(n) используются для вычисления других элементов в последовательности, если одна из дополнительных констант равна 1.
 Первые несколько членов последовательности F0,1 Пинна

  1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 7, 8, 8, 8, 8, 8, 8, 9, ...

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


 \texttt{Файл:ConwayChallengeSequence.jpgthumb300pxrightГрафик функции a(n)/n стремится к 0,5, как доказал КонвейДжон Хортон Конвей объявил о премии в \$10000 любому, кто продемонстрирует какой-либо результат об \texttt поведении последовательности. Премию, уменьшившуюся до \$1,000, получил Коллин Маллоуз }\texttt{. В частной беседе с Клаусом Пинном Хофштадтер позднее утверждал, что он нашёл последовательность и её структуру где-то за 10–15 лет до объявления Конвеем премии}\texttt{.}