En matemáticas , una secuencia de Hofstadter es un miembro de una familia de secuencias enteras relacionadas definidas por relaciones de recurrencia no lineal .
Las primeras sucesiones de Hofstadter fueron descritas por Douglas Richard Hofstadter en su libro Gödel, Escher, Bach . En orden de presentación en el capítulo III sobre figuras y fondo (secuencia Figura-Figura) y el capítulo V sobre estructuras y procesos recursivos (secuencias restantes), estas sucesiones son:
Las secuencias Figura-Figura de Hofstadter (R y S) son un par de secuencias enteras complementarias definidas de la siguiente manera [1] [2]
con la secuencia definida como una serie estrictamente creciente de números enteros positivos no presentes en . Los primeros términos de estas secuencias son
La secuencia G de Hofstadter se define de la siguiente manera [3] [4]
Los primeros términos de esta secuencia son
La secuencia H de Hofstadter se define de la siguiente manera [3] [5]
Los primeros términos de esta secuencia son
Las secuencias femenina (F) y masculina (M) de Hofstadter se definen de la siguiente manera [3] [6]
Los primeros términos de estas secuencias son
La secuencia Q de Hofstadter se define de la siguiente manera [3] [7]
Los primeros términos de la secuencia son
Hofstadter denominó 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]
Mientras que 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 hasta dónde hay que retroceder en la secuencia Q para encontrar los dos términos que se van a sumar. Por lo tanto, los índices de los términos de la suma dependen de la propia secuencia Q.
Q(1), el primer elemento de la secuencia, nunca es uno de los dos términos que se suman para producir un elemento posterior; sólo está involucrado 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, siendo g 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 en su mayoría en la generación g − 1 y solo unos pocos en la generación g − 2, pero nunca en una generación aún más antigua. [16]
La mayoría de estos hallazgos son observaciones empíricas, ya que hasta ahora prácticamente nada se ha demostrado rigurosamente sobre 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 punto porque su regla de generación intenta referirse a términos que conceptualmente se ubicarían a la izquierda del primer término Q(1). [12] [17] [19]
Veinte 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 renombraron 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 nos lleva a la familia de secuencias
donde s ≥ 2 y r < s .
Con ( r , s ) = (1,2), la secuencia Q original es miembro de esta familia. Hasta ahora, solo 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 se ha demostrado que la secuencia V, que no se comporta de manera tan caótica como las otras, no "muere". [19] De manera similar a la secuencia Q original , hasta la fecha prácticamente no se ha demostrado nada riguroso sobre la secuencia W. [19]
Los primeros términos de la secuencia V son
Los primeros términos de la secuencia W son
Para otros valores ( r , s ) las sucesiones tarde o temprano "mueren", es decir, existe un n para el cual Q r , s ( n ) no está definido porque n − Q r , s ( n − r ) < 1. [19]
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:
Así, Pinn introdujo constantes adicionales i y j que desplazan conceptualmente el índice de los términos de la suma hacia la izquierda (es decir, más cerca del inicio de la secuencia). [21]
Sólo 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 definidas. [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 alguna de las constantes adicionales es 1.
Los primeros términos de la secuencia Pinn F 0,1 son
La secuencia de $10,000 de Hofstadter–Conway se define de la siguiente manera [22]
Los primeros términos de esta secuencia son
Los valores convergen a 1/2, y esta secuencia adquirió su nombre porque John Horton Conway ofreció un premio de $10,000 a quien pudiera determinar su tasa de convergencia . El premio, reducido luego a $1,000, fue reclamado por Collin Mallows, quien demostró que [23] [24] En comunicación privada con Klaus Pinn, Hofstadter afirmó más tarde que había encontrado la secuencia y su estructura unos 10-15 años antes de que Conway planteara su desafío. [10]
