secuencia de Hofstadter

Las secuencias Figura-Figura de Hofstadter (R y S) son un par de secuencias de enteros complementarias definidas de la siguiente manera: ^{[ 1 ] [ 2 ]}

${\displaystyle {\begin{aligned}R(1)&=1,\ S(1)=2;\\R(n)&=R(n-1)+S(n-1),\quad n>1,\end{aligned}}}$

con la secuencia${\displaystyle S(n)}$definido como una serie estrictamente creciente de enteros positivos que no están presentes en${\displaystyle R(n)}$Los primeros términos de estas secuencias son:

R : 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236, 260,  ... (secuencia A005228 en el OEIS )

S : 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25,  ... (secuencia A030124 en el OEIS )

La secuencia G de Hofstadter se define de la siguiente manera: ^{[ 3 ] [ 4 ]}

${\displaystyle {\begin{aligned}G(0)&=0,\\G(n)&=nG{\big (}G(n-1){\big )},\quad n>0.\end{aligned}}}$

Los primeros términos de esta secuencia son

0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12,  ... (secuencia A005206 en el OEIS )

La secuencia H de Hofstadter se define de la siguiente manera: ^{[ 3 ] [ 5 ]}

${\displaystyle {\begin{aligned}H(0)&=0,\\H(n)&=nH{\Big (}H{\big (}H(n-1){\big )}{\Big )},\quad n>0.\end{aligned}}}$

Los primeros términos de esta secuencia son

0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14,  ... (secuencia A005374 en el OEIS )

Las secuencias femeninas ( F ) y masculinas ( M ) de Hofstadter se definen de la siguiente manera: ^{[ 3 ] [ 6 ]}

${\displaystyle {\begin{aligned}F(0)&=1,\ M(0)=0;\\F(n)&=nM{\big (}F(n-1){\big )},\quad n>0,\\M(n)&=nF{\big (}M(n-1){\big )},\quad n>0.\end{aligned}}}$

Los primeros términos de estas secuencias son

F : 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13,  ... (secuencia A005378 en el OEIS )

M : 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12,  ... (secuencia A005379 en el OEIS )

La secuencia Q de Hofstadter se define de la siguiente manera: ^{[ 3 ] [ 7 ]}

${\displaystyle {\begin{aligned}Q(1)&=Q(2)=1,\\Q(n)&=Q{\big (}nQ(n-1){\big )}+Q{\big (}nQ(n-2){\big )},\quad n>2.\end{aligned}}}$

Los primeros términos de la secuencia son

1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12,  ... (secuencia A005185 en el OEIS )

Hofstadter denominó a los términos de la secuencia "números Q"; ^{[ 3 ]} así, el número Q de 6 es 4. La presentación de la secuencia Q en el libro de Hofstadter es, de hecho, la primera mención conocida de una secuencia meta-Fibonacci en la literatura. ^{[ 8 ]}

Si bien los términos de la sucesión de Fibonacci se determinan sumando los dos términos precedentes, los dos términos precedentes de un número Q determinan hasta qué punto hay que retroceder en la sucesión Q para encontrar los dos términos que se van a sumar. Por lo tanto, los índices de los términos de la suma dependen de la propia sucesión Q.

Q (1), el primer elemento de la secuencia, nunca es uno de los dos términos que se suman para producir un elemento posterior; solo interviene dentro de un índice en el cálculo de Q (3). ^{[ 9 ]}

Aunque los términos de la secuencia Q parecen fluir caóticamente, ^{[ 3 ] [ 10 ] [ 11 ] [ 12 ]} como muchas secuencias meta-Fibonacci, sus términos pueden agruparse en bloques de generaciones sucesivas. ^{[ 13 ] [ 14 ]} En el caso de la secuencia Q, la k -ésima generación tiene 2 ^k miembros. ^{[ 15 ]} Además, siendo g la generación a la que pertenece un número Q, los dos términos que se suman para calcular el número Q, llamados sus padres, residen mayoritariamente en la generación g − 1 y solo unos pocos en la generación g − 2, pero nunca en una generación aún más antigua. ^{[ 16 ]}    

La mayoría de estos hallazgos son observaciones empíricas, ya que prácticamente no se ha demostrado nada sobre la secuencia Q hasta el momento. ^{[ 17 ] [ 18 ] [ 19 ]} Se desconoce específicamente si la secuencia está bien definida para todo n ; es decir, si la secuencia "muere" en algún punto porque su regla de generación intenta referirse a términos que conceptualmente se ubicarían a la izquierda del primer término Q (1). ^{[ 12 ] [ 17 ] [ 19 ]}

Veinte años después de que Hofstadter describiera por primera vez la secuencia Q , él y Greg Huber utilizaron el carácter Q para nombrar la generalización de la secuencia Q hacia una familia de secuencias, y renombraron la secuencia Q original de su libro como secuencia U. ^{[ 19 ]}

La secuencia Q original se generaliza reemplazando n  −  1 y n  −  2 por n  − r y n − s , respectivamente. ^{[ 19 ]}   

Esto da lugar a la familia de secuencias

${\displaystyle Q_{r,s}(n)={\begin{cases}1,\quad 1\leq n\leq s,\\Q_{r,s}(n-Q_{r,s}(nr))+Q_{r,s}(n-Q_{r,s}(ns)),\quad n>s,\end{cases}}}$

donde s  ≥  2 y r  < s . 

Con ( r , s ) = (1,2), la secuencia Q original pertenece a esta familia. Hasta ahora, solo se conocen tres secuencias de la familia Q _{r , s} , a saber, la secuencia U con ( r , s ) = (1,2) (que es la secuencia Q original); ^{[ 19 ]} la secuencia V con ( r , s ) = (1,4); ^{[ 20 ]} y la secuencia W con ( r , s ) = (2,4). ^{[ 19 ]} Solo la secuencia V, que no se comporta de forma tan caótica como las demás, ha demostrado no "morir". ^{[ 19 ]} De forma similar a la secuencia Q original , prácticamente no se ha demostrado nada rigurosamente sobre la secuencia W hasta la fecha. ^{[ 19 ]}

Los primeros términos de la secuencia V son

1, 1, 1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 11, ... (secuencia A063882 en el OEIS )

Los primeros términos de la secuencia W son

1, 1, 1, 1, 2, 4, 6, 7, 7, 5, 3, 8, 9, 11, 12, 9, 9, 13, 11, 9, ... (secuencia A087777 en el OEIS )

Para otros valores ( r , s ), las secuencias tarde o temprano "mueren", es decir, existe un n para el cual Q _{r , s} ( n ) no está definido porque n − Q _{r , s} ( n − r ) < 1. ^{[ 19 ]}      

En 1998, Klaus Pinn , científico de la Universidad de Münster (Alemania) y en estrecha comunicación con Hofstadter, sugirió otra generalización de la secuencia Q de Hofstadter que Pinn denominó secuencias F. ^{[ 21 ]}

La familia de secuencias Pinn F _{i , j} se define de la siguiente manera:

${\displaystyle F_{i,j}(n)={\begin{cases}1,\quad n=1,2,\\F_{i,j}(ni-F_{i,j}(n-1))+F_{i,j}(nj-F_{i,j}(n-2)),\quad n>2.\end{cases}}}$

Así, Pinn introdujo constantes adicionales i y j que desplazan conceptualmente el índice de los términos de la suma hacia la izquierda (es decir, más cerca del inicio de la secuencia). ^{[ 21 ]}

Solo las secuencias F con ( i , j ) = (0,0), (0,1), (1,0) y (1,1), la primera de las cuales representa la secuencia Q original , parecen estar bien definidas. ^{[ 21 ]} A diferencia de Q (1), los primeros elementos de las secuencias Pinn F _{i , j} ( n ) son términos de sumatorias al calcular elementos posteriores de las secuencias cuando cualquiera de las constantes adicionales es  1.

Los primeros términos de la secuencia Pinn F _0,1 son

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 9, 10, 10, 11, ... (secuencia A046699 en el OEIS )

• Balamohan, B.; Kuznetsov, A.; Tanny, Stephan M. (27 de junio de 2007), "Sobre el comportamiento de una variante de la secuencia Q de Hofstadter" (PDF) , Journal of Integer Sequences , 10 (7), Waterloo, Ontario (Canadá): University of Waterloo: 71, Bibcode : 2007JIntS..10...71B , ISSN 1530-7638 .
• Emerson, Nathaniel D. (17 de marzo de 2006), "Una familia de secuencias meta-Fibonacci definidas por recursiones de orden variable" (PDF) , Journal of Integer Sequences , 9 (1), Waterloo, Ontario (Canadá): Universidad de Waterloo, ISSN 1530-7638 .
• Hofstadter, Douglas (1980), Gödel, Escher, Bach: una eterna trenza dorada , Penguin Books, ISBN 0-14-005579-7.
• Pinn, Klaus (1999), "Orden y caos en la secuencia Q(n) de Hofstadter", 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.
• Pinn, Klaus (2000), "Un primo caótico de la secuencia recursiva de Conway", Matemáticas experimentales , 9 (1): 55– 66, arXiv : cond-mat/9808031 , Bibcode : 1998cond.mat..8031P , doi : 10.1080/10586458.2000.10504635 , S2CID 13519614 .