En matemáticas , una secuencia de Hofstadter es un miembro de una familia de secuencias enteras relacionadas definidas por relaciones de recurrencia no lineales .
Secuencias presentadas en Gödel, Escher, Bach: una eterna trenza dorada
Las primeras secuencias de Hofstadter fueron descritas por Douglas Richard Hofstadter en su libro Gödel, Escher, Bach . En el orden de su presentación en el capítulo III sobre figuras y antecedentes (secuencia Figura-Figura) y el capítulo V sobre estructuras y procesos recursivos (secuencias restantes), estas secuencias son:
Secuencias figura-figura de Hofstadter
Las secuencias Figura-Figura (R y S) de Hofstadter son un par de secuencias enteras complementarias definidas de la siguiente manera [1] [2]
con la secuencia definida como una serie estrictamente creciente de enteros positivos que no están presentes en . 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 )
Secuencia G de Hofstadter
La secuencia G de Hofstadter se define de la siguiente manera [3] [4]
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 )
Secuencia H de Hofstadter
La secuencia H de Hofstadter se define de la siguiente manera [3] [5]
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 )
Secuencias femeninas y masculinas de Hofstadter
Las secuencias de Hofstadter Femenino (F) y Masculino (M) se definen de la siguiente manera [3] [6]
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 la 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 la OEIS )
Secuencia Q de Hofstadter
La secuencia Q de Hofstadter se define de la siguiente manera [3] [7]
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 la OEIS )
Hofstadter nombró los términos de la secuencia "números Q"; [3] por lo tanto, el número Q de 6 es 4. La presentación de la secuencia Q en el libro de Hofstadter es en realidad la primera mención conocida de una secuencia meta-Fibonacci en la literatura. [8]
Si bien los términos de la secuencia de Fibonacci se determinan sumando los dos términos anteriores, los dos términos anteriores de un número Q determinan cuánto retroceder en la secuencia Q para encontrar los dos términos que se van a sumar. Por tanto, los índices de los términos de suma dependen de la secuencia Q misma.
Q (1), el primer elemento de la secuencia, nunca es uno de los dos términos que se agregan para producir un elemento posterior; está involucrado sólo 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, dado que g es la generación a la que pertenece un número Q, los dos términos que se deben sumar para calcular el número Q, llamados sus padres, residen, con mucho, principalmente en la generación g - 1 y solo unos pocos en la generación g - 2, pero nunca en una generación aún mayor. [dieciséis]
La mayoría de estos hallazgos son observaciones empíricas, ya que hasta ahora no se ha probado de manera rigurosa nada acerca de la secuencia Q. [17] [18] [19] Se desconoce específicamente si la secuencia está bien definida para todos los n ; es decir, si la secuencia "muere" en algún momento porque su regla de generación intenta referirse a términos que se ubicarían conceptualmente a la izquierda del primer término Q (1). [12] [17] [19]
Generalizaciones de la secuencia Q
Familia Hofstadter-Huber Q r , s ( n )
20 años después de que Hofstadter describiera por primera vez la secuencia Q , él y Greg Huber usaron el carácter Q para nombrar la generalización de la secuencia Q hacia una familia de secuencias, y cambiaron el nombre de la secuencia Q original de su libro a secuencia U. [19]
La secuencia Q original se generaliza reemplazando ( n - 1) y ( n - 2) por ( n - r ) y ( n - s ), respectivamente. [19]
Esto conduce a la familia de secuencias.
donde s ≥ 2 y r < s .
Con ( r , s ) = (1,2), la secuencia Q original es un miembro de esta familia. Hasta ahora, sólo 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 tan caóticamente como las otras, está probada para no "morir". [19] Al igual que en la secuencia Q original , prácticamente no se ha probado 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 la 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 la OEIS )
Para otros valores ( r , s ), las secuencias tarde o temprano "mueren", es decir, existe una n para la cual Q r , s ( n ) no está definida porque n - Q r , s ( n - r ) <1. [19]
Familia Pinn F i , j ( n )
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 llamó secuencias F. [21]
La familia de secuencias Pinn F i , j se define de la siguiente manera:
Por lo tanto, Pinn introdujo constantes adicionales i y j que desplazan el índice de los términos de la suma conceptualmente 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 definido. [21] A diferencia de Q (1), los primeros elementos de las secuencias Pinn F i , j ( n ) son términos de sumas en el cálculo de 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 la OEIS )
Secuencia de $ 10,000 de Hofstadter-Conway
La secuencia de $ 10,000 de Hofstadter-Conway se define de la siguiente manera [22]
Los primeros términos de esta secuencia son
- 1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, ... (secuencia A004001 en la OEIS )
Los valores convergen a 1/2, y esta secuencia adquirió su nombre porque John Horton Conway ofreció un premio de $ 10,000 a cualquiera que pudiera determinar su tasa de convergencia . El premio, que desde entonces se redujo a $ 1,000, fue reclamado por Collin Mallows , quien demostró que [23] [24]
Referencias
- ^ Hofstadter (1980) , p. 73
- ^ Weisstein, Eric W. "Secuencia figura-figura de Hofstadter" . MathWorld .
- ↑ a b c d e f Hofstadter (1980) , pág. 137
- ^ Weisstein, Eric W. "Hofstadter G-Sequence" . MathWorld .
- ^ Weisstein, Eric W. "Secuencia H de Hofstadter" . MathWorld .
- ^ Weisstein, Eric W. "Secuencias masculino-femenino de Hofstadter" . MathWorld .
- ^ Weisstein, Eric W. "Secuencia Q de Hofstadter" . MathWorld .
- ^ Emerson (2006) , págs. 1, 7
- ^ Pinn (1999) , págs. 5-6
- ↑ a b Pinn (1999) , p. 3
- ^ Pinn (2000) , pág. 1
- ↑ a b Emerson (2006) , p. 7
- ^ Pinn (1999) , págs. 3-4
- ^ Balamohan, Kuznetsov y Tanny (2007) , p. 19
- ^ Pinn (1999) , Resumen, p. 8
- ^ Pinn (1999) , págs. 4-5
- ↑ a b Pinn (1999) , p. 2
- ^ Pinn (2000) , pág. 3
- ↑ a b c d e f g h i Balamohan, Kuznetsov y Tanny (2007) , p. 2
- ^ Balamohan, Kuznetsov & Tanny (2007) , artículo completo
- ↑ a b c Pinn (2000) , pág. dieciséis
- ^ Weisstein, Eric W. "Secuencia de $ 10,000 de Hofstadter-Conway" . MathWorld .
- ^ Tempel, Michael. "Tan fácil como 1 1 2 2 3" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ Malvas, Colin L. (1991). "Secuencia de desafío de Conway". The American Mathematical Monthly . 98 (1): 5-20. doi : 10.2307 / 2324028 . JSTOR 2324028 . Señor 1083608 .
Fuentes
- Balamohan, B .; Kuznetsov, A .; Tanny, Stephan M. (2007-06-27), "Sobre el comportamiento de una variante de la secuencia Q de Hofstadter" (PDF) , Journal of Integer Sequences , Waterloo, Ontario (Canadá): Universidad de Waterloo, 10 , ISSN 1530 -7638.
- Emerson, Nathaniel D. (17 de marzo de 2006), "Una familia de secuencias de Meta-Fibonacci definidas por recursiones de orden variable" (PDF) , Journal of Integer Sequences , Waterloo, Ontario (Canadá): Universidad de Waterloo, 9 ( 1), ISSN 1530-7638.
- Hofstadter, Douglas (1980), Gödel, Escher, Bach: an Eternal Golden Braid , Penguin Books, ISBN 0-14-005579-7.
- Pinn, Klaus (1999), "Order and Chaos in Hofstadter's Q (n) Sequence", Complexity , 4 (3): 41-46, arXiv : chao-dyn / 9803012v2 , doi : 10.1002 / (SICI) 1099-0526 ( 199901/02) 4: 3 <41 :: AID-CPLX8> 3.0.CO; 2-3.
- Pinn, Klaus (2000), "A Chaotic Cousin of Conway's Recursive Sequence", Experimental Mathematics , 9 (1): 55–66, arXiv : cond-mat / 9808031 , Bibcode : 1998cond.mat..8031P.