Sucesión de Hofstadter

familia de sucesiones de números enteros propuestas y nombradas por Douglas 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

editar

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

editar

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 

 

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

Sucesión G de Hofstadter

editar

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

 

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)

Sucesión H de Hofstadter

editar

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

 

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

editar

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

 

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)

Sucesión Q de Hofstadter

editar

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

 

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 2k 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 

Generalizaciones de la sucesión Q

editar

Familia Hofstadter-Huber Qr, s(n)

editar

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

 

Donde   y  .

Con  , la sucesión original Q es un miembro de esta familia. Hasta ahora, solo se conocen tres sucesiones de la familia  , que son la sucesión U con   (que es la sucesión Q original);[10]: 2  la sucesión V con  [10]​ y la sucesión W con  [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   las sucesiones "mueren" tarde o temprano; es decir, existe una n para la cual   no está definida porque  

Familia Pinn Fi, j(n)

editar

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   de Pinn se define de la siguiente forma

 

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   (la primera de las cuales representa la sucesión Q original) aparentan estar bien definidas.[9]: 16  A diferencia de  , los primeros elementos de las sucesiones   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   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)

Sucesión Hofstadter-Conway de $10,000

editar

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

 

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 

Referencias

editar
  1. a b Hofstadter, Douglas R. (1980). Gödel, Escher, Bach : an Eternal Golden Braid (en inglés estadounidense). Penguin. ISBN 0140179976. OCLC 10399586. Consultado el 10 de octubre de 2019. 
  2. Weisstein, Eric W. «Hofstadter Figure-Figure Sequence». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
  3. Weisstein, Eric W. «Hofstadter G-Sequence». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
  4. Weisstein, Eric W. «Hofstadter H-Sequence». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
  5. Weisstein, Eric W. «Hofstadter Male-Female Sequences». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
  6. a b c Weisstein, Eric W. «Hofstadter's Q-Sequence». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
  7. a b c Emerson, Nathaniel D. (17 de marzo de 2006). «A Family of Meta-Fibonacci sequences Defined by Variable-Order Recursions» (PDF). Journal of Integer Sequences (Waterloo, Ontario (Canadá): Universidad de Waterloo) 9 (1): 1, 7. ISSN 1530-7638. 
  8. a b c d e f g h Pinn, Klaus (1999). «Order and chaos in Hofstadter's Q(n) sequence». Complexity (en inglés) 4 (3): 41-46. ISSN 1099-0526. doi:10.1002/(SICI)1099-0526(199901/02)4:33.0.CO;2-3. Consultado el 10 de octubre de 2019. 
  9. a b c d e Pinn, K. (4 de agosto de 1998). «A Chaotic Cousin Of Conway's Recursive Sequence». arXiv:cond-mat/9808031. Consultado el 10 de octubre de 2019. 
  10. a b c d e f g h i Balamohan, B.; Kuznetsov, A.; Tanny, Stephan M. (27 de junio de 2007). «On the Beabious of a Variant of Hofstadter's Q-Sequence» (PDF). Journal of Integer Sequences (Waterloo, Ontario (Canadá): University of Waterloo) 10. ISSN 1530-7638. 
  11. Weisstein, Eric W. «Hofstadter-Conway $10,000 Sequence». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
  12. Tempel, Michael. Easy as 1 1 2 2 3.