secuencia de Hofstadter
En matemáticas , una secuencia de Hofstadter es un miembro de una familia de secuencias enteras relacionadas definidas por relaciones de recurrencia no lineales .
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 fondo (secuencia Figura-Figura) y el capítulo V sobre estructuras y procesos recursivos (secuencias restantes), estas secuencias 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 enteros positivos que no están presentes en . Los primeros términos de estas sucesiones son
Hofstadter llamó a 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 de meta-Fibonacci en la literatura. [8]
Mientras que los términos de la sucesión 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 sucesión Q para encontrar los dos términos que se van a sumar. Los índices de los términos de la suma dependen, por lo tanto, de la propia secuencia Q.