Sucesión de Hofstadter

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)

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

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

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, ... (sucesión A004001 en 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.^[12] 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.^[8]: 3

• Esta obra contiene una traducción derivada de «Hofstadter Sequence» de Wikipedia en inglés, concretamente de esta versión del 19 de junio de 2018, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.