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

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

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

В 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, 3, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 9, 10, 10, 11, ... последовательность A046699 в OEIS