Sucesión de Hofstadter

En matemáticas, una sucesión de Hofstadter es un miembro de una familia de sucesiones de números enteros relacionadas entre sí y definidas por relaciones de recurrencias no lineales.

Sucesiones presentadas en Gödel, Escher, Bach: un Eterno y Grácil Bucle

Las primeras sucesiones de Hofstadter fueron descritas por Douglas Richard Hofstadter en su libro Gödel, Escher, Bach. En orden de su presentación en el capítulo III sobre las figuras y el fondo (sucesión Figura-a-Figura) y en el capítulo V sobre estructuras y procesos recursivos (sucesiones de "residuo"), estas sucesiones son:

Sucesiones de Hofstadter Figura-a-Figura

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 formaPlantilla:Rp

$\begin{array}{cc}R(1)& =1;S(1)=2\\ R(n)& =R(n-1)+S(n-1),n>1.\end{array}$

en el que la sucesión $S(n)$ se define como una serie estrictamente creciente de números enteros positivos que no están presentes en $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,... Plantilla:OEIS

S: 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25,... Plantilla:OEIS

Sucesión G de Hofstadter

La sucesión G de Hofstadter se define de la siguiente formaPlantilla:Rp

$\begin{array}{cc}G(0)& =0\\ G(n)& =n-G(G(n-1)),n>0.\end{array}$

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, ... Plantilla:OEIS

Sucesión H de Hofstadter

La sucesión H de Hofstadter se define de la siguiente forma

$\begin{array}{cc}H(0)& =0\\ H(n)& =n-H(H(H(n-1))),n>0.\end{array}$

Los primeros términos de esta sucesión son

0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14, ... {{OEIS|id=A005374}}

Sucesiones Femenina y Masculina de Hofstadter

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

$\begin{array}{cc}F(0)& =1;M(0)=0\\ F(n)& =n-M(F(n-1)),n>0\\ M(n)& =n-F(M(n-1)),n>0.\end{array}$

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, ... Plantilla:OEIS

M: 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 1, 1, 12, 12, ... Plantilla:OEIS

Sucesión Q de Hofstadter

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

$\begin{array}{cc}Q(1)& =Q(2)=1,\\ Q(n)& =Q(n-Q(n-1))+Q(n-Q(n-2)),n>2\end{array}$

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, ... Plantilla:OEIS

Hofstadter nombró a los términos de esta sucesión «números Q», 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.

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).Plantilla:Rp

Aunque los términos de la sucesión Q aparentan ser caóticos,Plantilla:RpPlantilla:Rp es posible agrupar sus términos en bloques de generaciones sucesivas, al igual que otras meta-sucesiones de Fibonacci.Plantilla:Rp En el caso de la sucesión Q, la k-ésima generación tiene 2^k miembros.Plantilla:Rp 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.Plantilla:Rp

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 ahoraPlantilla:RpPlantilla:RpPlantilla:Rp 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).Plantilla:RpPlantilla:Rp<nowiki>Plantilla:Rp

Generalizaciones de la sucesión Q

Familia Hofstadter-Huber Q_{r, s}(n)

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 UPlantilla:Rp

La sucesión original Q se generaliza al reemplazar (n − 1) y (n − 2) por (n − r) y (n − s) respectivamente.Plantilla:Rp

Esto lleva a la familia de sucesiones

$Q_{r,s}(n)=\{\begin{array}{c}1,1\le n\le s,\\ Q_{r,s}(n-Q_{r,s}(n-r))+Q_{r,s}(n-Q_{r,s}(n-s)),n>s,\end{array}$

Donde $s\ge 2$ y $r<s$.

Con $(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 $Q_{r,s}$, que son la sucesión U con $(r,s)=(1,2)$ (que es la sucesión Q original);Plantilla:Rp la sucesión V con $(r,s)=(1,4)$ y la sucesión W con $(r,s)=(2,4)$Plantilla:Rp 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.

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, ... Plantilla: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, ... Plantilla:OEIS

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

Familia Pinn F_{i, j}(n)

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.Plantilla:Rp

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

$F_{i,j}(n)=\{\begin{array}{c}1,n=1,2,\\ F_{i,j}(n-i-F_{i,j}(n-1))+F_{i,j}(n-j-F_{i,j}(n-2)),n>2.\end{array}$

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).Plantilla:Rp

Solo las sucesiones F con $(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.Plantilla:Rp A diferencia de $Q(1)$, los primeros elementos de las sucesiones $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 $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, ... Plantilla:OEIS

Sucesión Hofstadter-Conway de $10,000

La sucesión Hofstadter-Conway de $10,000 dólares se define de la siguiente forma

$\begin{array}{cc}a(1)& =a(2)=1,\\ A(n)& =a(a(n-1))+a(n-a(n-1)),n>2\end{array}$

Los primeros términos de esta sucesión son

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, ... Plantilla:OEIS

La sucesión recibe su nombre por el premio de $10,000 dólares que John Horton Conway ofreció a cualquiera que pudiese demostrar un resultado particular acerca de su comportamiento asintótico. El premio, posteriormente reducido a $1,000, fue cobrado por Collin Mallows. En comunicación privada con Klaus Pinn, Hofstadter afirmó que había encontrado la sucesión y su estructura entre 10 y 15 años antes de que Conway presentara su reto.Plantilla:Rp