Processing math: 100%

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

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

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


 Первые последовательности Хофштадтера описал Дуглас Хофштадтер в своейкниге Гёдель, Эшер, Бах. Последовательности показаны в порядке ихпредставления в главе 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{.}