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

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

, представленные в книгах Гёделя, Эшера, Баха: Вечная

Первые последовательности Хофштадтера были описаны Дугласом Рихардом Хофштадтером в его книге «Гёдель, Эшер, Бах» . В порядке их представления в главе III, посвященной рисункам и фону (последовательность «Рисунок-рисунок») и главе V, посвященной рекурсивным структурам и процессам (остальные последовательности), эти последовательности таковы:

фигур-

Последовательности «фигура-фигура» Хофштадтера (R и S) представляют собой пару дополнительных целочисленных последовательностей, определенных следующим образом.

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

S: 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, ... (последовательность A030124 в ОЭИС )

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

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

${\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 в ОЭИС )

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

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

${\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 в ОЭИС )

и

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

${\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 в ОЭИС )

М: 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, ... (последовательность A005379 в ОЭИС )

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

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

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

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

Q(1), первый элемент последовательности, никогда не является одним из двух членов, добавляемых для создания последующего элемента; он участвует только в пределах индекса при расчете Q(3).

Хотя члены последовательности Q кажутся хаотичными, как и многие последовательности мета-Фибоначчи, ее члены могут быть сгруппированы в блоки последовательных поколений. В случае Q-последовательности k -е поколение имеет 2 ^к члены. Кроме того, поскольку g является поколением, к которому принадлежит число Q, два члена, которые необходимо суммировать для вычисления числа Q, называемые его родителями, в основном находятся в поколении g - 1 и лишь немногие - в поколении g - 2, но никогда в даже старшем поколении.

практически ничего не было строго доказано в отношении последовательности Q. Большинство этих результатов являются эмпирическими наблюдениями, поскольку до сих пор В частности, неизвестно, определена ли последовательность для всех n ; то есть, если последовательность «умирает» в какой-то момент, потому что ее правило генерации пытается ссылаться на термины, которые концептуально будут располагаться слева от первого термина Q (1).

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

Хофштадтера-Хубера Qr _{( , s} Семья n )

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

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

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

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

Пинн Фи _{, n j} ( ) Семья

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

Семейство последовательностей Pinn F _{i , j} определяется следующим образом:

$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), первые элементы последовательностей Pinn 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 )

Хофштадтера-Конвея стоимостью 10

Последовательность Хофштадтера – Конвея стоимостью 10 000 долларов определяется следующим образом. $${\begin{aligned}a(1)&=a(2)=1,\\a(n)&=a{\big (}a(n-1){\big )}+a{\big (}n-a(n-1){\big )},\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 )

Ценности $a(n)/n$ сходятся к 1/2, и свое название эта последовательность получила потому, что Джон Хортон Конвей предложил приз в размере 10 000 долларов тому, кто сможет определить скорость ее сходимости . Приз, уменьшенный до 1000 долларов, получил Коллин Мэллоуз , доказавший, что $$\left|{\frac {a(n)}{n}}-{\frac {1}{2}}\right|=O\left({\frac {1}{\sqrt {\log n}}}\right).$$В частном общении с Клаусом Пинном Хофштадтер позже утверждал, что нашел последовательность и ее структуру примерно за 10–15 лет до того, как Конвей поставил перед собой задачу.

Ссылки

Источники

• Баламохан, Б.; Кузнецов А.; Тэнни, Стефан М. (27 июня 2007 г.), «О поведении варианта Q-последовательности Хофштадтера» (PDF) , Журнал целочисленных последовательностей , 10 (7), Ватерлоо, Онтарио (Канада): Университет Ватерлоо : 71, Bibcode : 2007JIntS..10...71B , ISSN   1530-7638 .
• Эмерсон, Натаниэль Д. (17 марта 2006 г.), «Семейство последовательностей мета-Фибоначчи, определяемых рекурсиями переменного порядка» (PDF) , Журнал целочисленных последовательностей , 9 (1), Ватерлоо, Онтарио (Канада): Университет Ватерлоо, ISSN   1530-7638 .
• Хофштадтер, Дуглас (1980), Гёдель, Эшер, Бах: вечная золотая коса , Penguin Books, ISBN  0-14-005579-7 .
• Пинн, Клаус (1999), «Порядок и хаос в последовательности Q(n) Хофштадтера», Complexity , 4 (3): 41–46, arXiv : chao-dyn/9803012v2 , Bibcode : 1999Cmplx...4c..41P , doi : 10.1002/(SICI)1099-0526(199901/02)4:3<41::AID-CPLX8>3.0.CO;2-3 .
• Пинн, Клаус (2000), «Хаотический родственник рекурсивной последовательности Конвея», Experimental Mathematics , 9 (1): 55–66, arXiv : cond-mat/9808031 , Bibcode : 1998cond.mat..8031P , doi : 10.1080/ 10586458.2000.10504635 , S2CID   13519614 .