Secuencia de Hofstadter

La secuencia de Hofstadter es una de una familia de secuencias enteras definidas por fórmulas recurrentes no lineales .

Secuencias de Gödel, Escher, Bach: esta guirnalda interminable

Las primeras secuencias de Hofstadter fueron descritas por Douglas Hofstadter en su libro Gödel, Escher, Bach . Las secuencias se muestran en el orden de su presentación en el Capítulo III sobre figuras y fondo (secuencia Figura-Figura) y en el Capítulo V sobre estructuras y procesos recursivos (otras secuencias).

Secuencias Dibujo-Dibujo de Hofstadter

Las secuencias Hofstadter Drawing-Drawing ( R y S ) son un par de secuencias enteras complementarias . La secuencia { R } se define de la siguiente manera [1] [2]

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

y la secuencia {S( n )} se define como una secuencia estrictamente creciente de enteros positivos que no están presentes en {R( n )}. Los primeros términos de estas sucesiones

R: 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236, 260, ... ( secuencia OEIS A005228 ) S: 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, ... ( secuencia OEIS A030124 )

Secuencia G de Hofstadter

La secuencia de Hofstadter G se define de la siguiente manera [3] [4]

{\begin{alineado}G(0)&=0\\G(n)&=nG(G(n-1)),\quad n>0.\end{alineado))

Los primeros términos de esta secuencia

0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, ... ( secuencia OEIS A005206 )

La secuencia de Hofstadter H

La secuencia de Hofstadter H se define de la siguiente manera [3] [5]

{\begin{alineado}H(0)&=0\\H(n)&=nH(H(H(n-1))),\quad n>0.\end{alineado))

Los primeros términos de esta secuencia

0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14, ... ( secuencia OEIS A005374 )

Secuencias femeninas y masculinas de Hofstadter

Las secuencias de Hofstadter femenina (F) y masculina (M) se definen de la siguiente manera [3] [6]

{\begin{alineado}F(0)&=1~;\ M(0)=0\\M(n)&=nF(M(n-1)),\quad n>0\\ F(n)&=nM(F(n-1)),\quad n>0.\end{alineado}}

Los primeros términos de estas sucesiones

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 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 OEIS )

Secuencia Q de Hofstadter

La sucesión de Hofstadter Q se define de la siguiente manera [3] [7] :

{\begin{alineado}Q(1)&=Q(2)=1,\\Q(n)&=Q(nQ(n-1))+Q(nQ(n-2)), \quad n>2.\end{alineado}}

Los primeros términos de esta secuencia

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

Hofstadter llamó a los términos de la secuencia "Q-numbers" [3] . Así, el sexto número de Q es 4. La representación de la secuencia Q en el libro de Hofstadter es, de hecho, la primera mención de las metasecuencias de Fibonacci en la literatura [8] .

Mientras que los números de Fibonacci se determinan sumando los dos términos anteriores, los dos términos anteriores de la sucesión Q determinan qué tan atrás tienes que ir para tomar los términos de la sucesión para sumar. Los índices para la suma vienen dados por la misma sucesión Q.

Q(1), el primer elemento de la secuencia, solo se usa para calcular Q(3) [9] .

Aunque la secuencia Q parece caótica [3] [10] [11] [12] , como muchas otras metasecuencias de Fibonacci, sus miembros se pueden agrupar en bloques [13] [14] . Para la secuencia Q, el k -ésimo bloque tiene 2 k miembros [15] . Además, para g que pertenece al bloque al que pertenece el número Q, los dos términos utilizados para calcular el número Q, llamados padres, están en su mayoría en el bloque g − 1 y solo unos pocos miembros están en el bloque g − 2, pero nunca en bloques anteriores [16] .

La mayoría de estos hallazgos son observaciones empíricas, ya que nada se ha probado rigurosamente sobre la secuencia Q hasta la fecha [17] [18] [19] . En particular, no se sabe si la sucesión está bien definida para todo n . Es decir, ¿la secuencia "muere" en algún momento al intentar usar el miembro de la secuencia a la izquierda del primer miembro de Q(1)? [12] [17] [19]

Un ejemplo para entender el algoritmo:

por ejemplo, es necesario sustituir los valores Q(1) = 1, Q(2)=1 (por condición).

Q(3) = Q(3-1)+Q(3-1) = Q(2)+ Q(2) = 2

Q(4) = (Q(4-Q(3))+Q(4-Q(2)) = Q(4-2)+Q(4-1) = Q(2)+Q(3) = 1+2=3

Generalizaciones de la secuencia Q

La familia Hofstadter-Huber Q r , s ( n )

20 años después de la descripción de Hofstadter de la secuencia Q , Hofstadter y Greg Huber usaron el símbolo Q para generalizar la secuencia Q a una familia de secuencias, y la secuencia original Q pasó a llamarse secuencia U [19] .

La secuencia original Q se generaliza reemplazando ( n − 1) y ( n − 2) con ( n − r ) y ( n − s ) respectivamente [19] .

Esto resultó en una familia de secuencias

Q_{r,s}(n)={\begin{casos}1,\quad 1\leq n\leq s,\\Q_{r,s}(n-Q_{r,s}(nr ))+Q_{r,s}(n-Q_{r,s}(ns)),\quad n>s,\end{casos}}

donde s ≥ 2 y r < s .

Para ( r , s ) = (1,2) obtenemos la secuencia original Q , por lo que es miembro de esta familia. Actualmente, solo se conocen tres secuencias de la familia Q r , s , a saber, la secuencia U con ( r , s ) = (1,2) (la secuencia original Q ) [19] , la secuencia V con ( r , s ) = (1 ,4) [20] y una secuencia W con (r,s) = (2,4) [19] . Sólo para la secuencia V , que no se comporta tan caóticamente como las otras dos, se prueba que no "muere" [19] . Al igual que la sucesión Q original , no se ha probado nada estrictamente para la sucesión W [19] .

Varios primeros términos de la sucesión V

1, 1, 1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 11, ... ( secuencia OEIS A063882 )

Varios primeros términos de la sucesión W

1, 1, 1, 1, 2, 4, 6, 7, 7, 5, 3, 8, 9, 11, 12, 9, 9, 13, 11, 9, ... ( secuencia OEIS A087777 )

Para otros valores ( r , s ) las secuencias "mueren" tarde o temprano, es decir existe n para el cual el valor de Qr , s ( n ) no está definido porque n − Qr , s ( norte - r ) < 1 [19] .

Una familia de sucesiones F i , j ( n )

En 1998, Klaus Pinn, un científico de la Universidad de Münster (Alemania), en estrecho contacto con Hofstadter, propuso otra generalización de la secuencia Q de Hofstadter , y llamó a las secuencias resultantes secuencias F [ 21] .

La familia de secuencias de Pinn F i , j se define como sigue:

F_{i,j}(n)={\begin{casos}1,\quad n=1,2,\\F_{i,j}(ni-F_{i,j}(n-1 ))+F_{i,j}(nj-F_{i,j}(n-2)),\quad n>2.\end{casos}}

Por lo tanto, Pinn introdujo constantes adicionales i y j , que desplazan los índices de los términos sumados hacia la izquierda (es decir, más cerca del comienzo de la secuencia) [21] .

Sólo las sucesiones F con ( i , j ) = (0,0), (0,1), (1,0) y (1,1), la primera de las cuales es la sucesión original Q , resultan ser bien- definido [21] . A diferencia de Q (1), los primeros elementos de las secuencias de Pinn F i , j ( n ) se utilizan para calcular los otros elementos de la secuencia si una de las constantes adicionales es 1.

Los primeros términos de la sucesión F 0.1 Pinn

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 9, 10, 10, 11, ... Secuencia OEIS A046699

$ 10,000 Secuencia Hofstadter-Conway

La secuencia Hofstadter-Conway de $ 10,000 se define de la siguiente manera [22]

{\begin{alineado}a(1)&=a(2)=1,\\a(n)&=a(a(n-1))+a(na(n-1)), \quad n>2.\end{alineado}}

Los primeros términos de la sucesión.

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, … (secuencia A004001 en OEIS )

La secuencia recibió su nombre porque John Horton Conway anunció un bono de $10,000 a cualquiera que pudiera demostrar un cierto resultado sobre el comportamiento asintótico de la secuencia. El premio, reducido a $1,000, fue para Collin Mallows [23] . En una conversación privada con Klaus Pinn, Hofstadter afirmó más tarde que encontró la secuencia y su estructura unos 10-15 años antes del anuncio del premio por parte de Conway [10] .

Notas

↑ Hofstadter, 1980 , pág. 73.
↑ Weisstein, Eric W. Hofstadter Figure-Figure Sequence en el sitio web de Wolfram MathWorld .
↑ 1 2 3 4 5 6 Hofstadter, 1980 , pág. 137.
↑ Weisstein, Eric W. Hofstadter G-Sequence en el sitio web de Wolfram MathWorld .
↑ Weisstein, Eric W. Hofstadter H-Sequence en el sitio web de Wolfram MathWorld .
↑ Weisstein, Eric W. Hofstadter Secuencias macho-hembra en el sitio web Wolfram MathWorld .
↑ Weisstein, Q-Sequence de Eric W. Hofstadter en el sitio web Wolfram MathWorld .
↑ Emerson, 2006 , pág. 1, 7.
↑ Pinn, 1999 , pág. 5–6.
↑ 12 Pinn , 1999 , pág. 3.
↑ Pinn, 2000 , pág. una.
↑ 12 Emerson , 2006 , pág. 7.
↑ Pinn, 1999 , pág. 3–4.
↑ Balamohan, Kuznetsov, Tanny, 2007 , pág. 19
↑ Pinn, 1999 , pág. resumen, 8.
↑ Pinn, 1999 , pág. 4–5.
↑ 12 Pinn , 1999 , pág. 2.
↑ Pinn, 2000 , pág. 3.
↑ 1 2 3 4 5 6 7 8 9 Balamohan, Kuznetsov, Tanny, 2007 , pág. 2.
↑ Balamohan, Kuznetsov, Tanny, 2007 .
↑ 1 2 3 Pinn, 2000 , pág. dieciséis.
↑ Weisstein, Eric W. Hofstadter-Conway $10,000 Sequence en el sitio web de Wolfram MathWorld .
↑ Templo .

Literatura

Miguel Tempel. Fácil como 1 1 2 2 3 . (indefinido)
B. Balamohan, A. Kuznetsov, Stephan M. Tanny. Sobre el comportamiento de una variante de la secuencia Q de Hofstadter . — Revista de secuencias enteras. - Waterloo, Ontario (Canadá): University of Waterloo, 2007. - Vol. 10.
Nathaniel D. Emerson. [1530-7638 Una familia de secuencias de Meta-Fibonacci definidas por recursiones de orden variable]. — Revista de secuencias enteras. - Waterloo, Ontario (Canadá): Universidad de Waterloo, 2006. - V. 9.
Douglas Hofstadter. Gödel, Escher, Bach: una eterna trenza dorada. - Libros de pingüinos, 1980. - ISBN 0-14-005579-7 .
Klaus Pin. Orden y Caos en la Secuencia Q(n) de Hofstadter // Complejidad. - 1999. - T. 4 , nº. 3 . — págs. 41–46 . -doi : 10.1002 / (SICI)1099-0526(199901/02)4:3<41::AID-CPLX8>3.0.CO;2-3 . -arXiv : chao - dyn/9803012v2 .
Klaus Pin. Un primo caótico de la secuencia recursiva de Conway // Matemáticas experimentales . - 2000. - T. 9 , núm. 1 . — S. 55–66 . -arXiv : cond - mat/9808031 .