Sucesión de Hofstadter

Las sucesiones de Hofstadter de Figura-a-Figura (R y S) son una pareja de sucesiones complementarias de números enteros que se definen de la siguiente forma[1][2]^: 73

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

en el que la sucesión ${\displaystyle S(n)}$ se define como una serie estrictamente creciente de números enteros positivos que no están presentes en ${\displaystyle R(n)}$. Los primeros términos de estas sucesiones son:

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

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

La sucesión G de Hofstadter se define de la siguiente forma[1]^: 137[3]

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

Los primeros términos de esta sucesión son

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

Las sucesiones Femenina (F) y Masculina (M) de Hofstadter se definen de la siguiente forma[5]

${\displaystyle {\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}}}$

Los primeros términos de estas sucesiones son

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

M: 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 1, 1, 12, 12, ... (sucesión A005379 en OEIS)

La sucesión Q de Hofstadter se define de la siguiente forma[6]

${\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}}}$

Los primeros términos de esta sucesión son

1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, ... (sucesión A005185 en OEIS)

Hofstadter nombró a los términos de esta sucesión «números Q»;[6], de tal forma que el número Q de 6 es 4. La presentación de la sucesión Q en el libro de Hofstadter es de hecho la primera mención conocida de una Meta-sucesión de Fibonacci en la literatura.[7]

Mientras que los términos de la Sucesión de Fibonacci se determinan al sumar los dos términos precedentes, los dos términos precedentes de un número Q determinan qué tan "atrás" hay que ir en la sucesión Q para encontrar los dos términos a ser sumados. Por lo tanto, los índices de los términos de la suma dependen en la sucesión Q en sí misma.

Q(1), el primero elemento de la sucesión, nunca es uno de los dos términos que se añaden para producir un término posterior; solo se le usa como un índice en el cálculo de Q(3).[8]^: 1, 7

Aunque los términos de la sucesión Q aparentan ser caóticos,[6][8]^: 3[9][7]^: 7 es posible agrupar sus términos en bloques de generaciones sucesivas, al igual que otras meta-sucesiones de Fibonacci.[8]^: 3–4[10] En el caso de la sucesión Q, la k-ésima generación tiene 2^k miembros.[8]^: 8 Más aún, dada la generación g a la que pertenece un número Q, los dos términos a ser sumados para calcular el número Q, llamados sus padres, residen con mayor probabilidad en la generación g − 1 y solo unos pocos en la generación g − 2, pero nunca en una generación aún anterior.[8]^: 4–5

La mayoría de estas observaciones son empíricas, ya que prácticamente no se ha probado rigorosamente nada acerca de la sucesión Q hasta ahora[8]^: 2[9]^: 3[10]^: 2 En particular, se desconoce si la sucesión está bien definida para todo n; es decir, si la sucesión "muere" en algún punto debido a que la regla de su generación intente referirse a términos que conceptualmente estarían «a la izquierda» de Q(1).[7]^: 7[8]^: 2<nowiki>[10]^: 2

20 años después de que Hofstadter describiera por primera vez la sucesión Q, él y Greg Huber usaron el carácter Q para numbrar la generalización de la sucesión Q hacia una familia de sucesiones, y renombraron la sucesión original del libro como la sucesión U[10]^: 2

La sucesión original Q se generaliza al reemplazar (n − 1) y (n − 2) por (n − r) y (n − s) respectivamente.[10]^: 2

Esto lleva a la familia de sucesiones

${\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}}}$

Donde ${\displaystyle s\geq 2}$ y ${\displaystyle r<s}$.

Con ${\displaystyle (r,s)=(1,2)}$, la sucesión original Q es un miembro de esta familia. Hasta ahora, solo se conocen tres sucesiones de la familia ${\displaystyle Q_{r,s}}$, que son la sucesión U con ${\displaystyle (r,s)=(1,2)}$ (que es la sucesión Q original);[10]^: 2 la sucesión V con ${\displaystyle (r,s)=(1,4)}$[10] y la sucesión W con ${\displaystyle (r,s)=(2,4)}$[10]^: 2 Solo para la sucesión V, cuyo comportamiento no es tan caótico como las otras, se ha probado que no "muere". De forma similar a la sucesión original Q, poco se ha probado rigurosamente acerca de la sucesión W hasta ahora.[10]

Los primeros términos de la sucesión V son

1, 1, 1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 11, ... (sucesión A0638882 en OEIS)

Los primeros términos de la sucesión W son

1, 1, 1, 1, 2, 4, 6, 7, 7, 5, 3, 8, 9, 11, 12, 9, 9, 13, 11, 9, ... (sucesión A087777 en OEIS)

Para otros valores ${\displaystyle (r,s)}$ las sucesiones "mueren" tarde o temprano; es decir, existe una n para la cual ${\displaystyle Q_{r,s}(n)}$ no está definida porque ${\displaystyle n-Q_{r,s}(n-r)<1}$

En 1998, Klaus Pinn, científico en la Universidad de Münster (Alemania) en comunicación con Hofstadter, sugirió otra generalización de la sucesión Q de Hofstadter, que Pinn denominó sucesiones F.[9]^: 16

La familia de sucesiones ${\displaystyle F_{i,j}}$ de Pinn se define de la siguiente forma

${\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}}}$

De esta forma Pin introdujo constantes adicionales (i, j) que cambian conceptualmente el índice de los términos de la suma hacia la izquierda (esto es, más cercanos al inicio de la sucesión).[9]^: 16

Solo las sucesiones F con ${\displaystyle (i,j)=(0,0),(0,1),(1,0),(1,1)}$ (la primera de las cuales representa la sucesión Q original) aparentan estar bien definidas.[9]^: 16 A diferencia de ${\displaystyle Q(1)}$, los primeros elementos de las sucesiones ${\displaystyle F_{i,j}(n)}$ de Pinn son términos de suma para calcular elementos posteriores de las sucesiones cuando cualquiera de las constantes adicionales es igual a 1.

Los primeros términos de la sucesión ${\displaystyle F_{0,1}}$ de Pinn son

1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 7, 8, 8, 8, 8, 8, 8, 9, ... (sucesión A055748 en OEIS)