Douglas Hofstadter's sequences

The first of these sequences is from the book 'Gödel Escher Bach' by Douglas Hofstadter. It is "The Hofstadter Q-sequence" A005185 in the enciclopedy of N.J.A. Sloane.
Like the Fibonacci and Lucas sequences, each term is the sum of two preceding terms, but not the two last terms:

Q(1) = Q(2) = 1 et pour n > 2, Q(n) = Q(n-Q(n-1)) + Q(n-Q(n-2))

(The definition of Fibonacci is simpler : F(n) = F(n-1) + F(n-2)).

Hofstadter's Q-sequence

Terms of indices 1 to 200 000 (or 3 500) of the Q-sequence

Example : calculation of Q(18)
Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)), the two terms Q(n-1) and Q(n-2), give two shifts starting from N allowing to find the indices n-Q(n-1) et n-Q(n-2) of the two terms to be added.

The first terms are Q(1)=1, 1, 2, 3, 3, 4, 5, Q(8)=5, Q(9)=6, 6, 6, 8, 8, 8, 10, Q(16)=9, Q(17)=10, Q(18)= ...

To calculate Q(18), it is observed that the two preceding elements are Q(17)=10 and Q(16)=9. Instead of adding these two numbers, as one would have done for Fibonacci, one shifts of 10 and 9 starting from row 18 : in 18-10=8 and 18-9=9, the two values to be added are Q(8)=5 and Q(9)=6, from where Q(18)=5+6=11.

The sequence has a moderately erratic behavior, perhaps chaotic, but it is not certain, the graphs let think of a certain form of regularity.

Sequence Q(n) for n in the range [a ; b]

a =     b =   

Page with the java applet

These sequences can have similar behaviors or not.
Select that whose you want to calculate terms.

Choice of the sequence

Hofstadter Q(1)=Q(2)=1, Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)) A005185    Hofstadter-Conway a(1)=a(2)=1, a(n)=a(a(n-1))+a(n-a(n-1)) A004001    Hofstadter G-sequence: a(0)=0, a(1)=1, a(n)=n-a(a(n-1)) A005206    Hofstadter H-sequence: a(0)=0, a(n)=n-a(a(a(n-1))) A005374    Hofstadter type : a(0)=0, a(n)=n-a(a(a(a(n-1)))) A005375    Hofstadter type : a(0)=0, a(n)=n-a(a(a(a(a(n-1))))) A005376    Reg Allenby : a(1) = a(2) = 1, a(n) = a(n - a(n-1)) + a(n-1 - a(n-2)) A046699    K. Pinn : A chaotic cousin of Conway's recursive sequence, a(1)=a(2)=1, a(n)=a(a(n-1))+a(n-1-a(n-2)) A046699    S. M. Tanny : A well-behaved cousin of the Hofstadter sequence, a(0)=a(1)=a(2)=1, a(n)=a(n-1-a(n-1))+a(n-2-a(n-2)) A006949    Hofstadter-type sequence : a(1)=a(2)=1, a(n)=2+a(n-a(n-1)) A070864

Calculation

To obtain all the terms whose rows go m to N, write these two terminals, and click.