The Hofstadter Q sequence is defined as:

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

It is defined like the Fibonacci sequence, but whereas the next term in the Fibonacci sequence is the sum of the previous two terms, in the Q sequence the previous two terms tell you how far to go back in the Q sequence to find the two numbers to sum to make the next term of the sequence.

• Confirm and display that the first ten terms of the sequence are: 1, 1, 2, 3, 3, 4, 5, 5, 6, and 6
• Confirm and display that the 1000th term is: 502

#include <iostream>

int main( ) {
hofstadters[ 0 ] = 1 ;
hofstadters[ 1 ] = 1 ;
for ( int i = 3 ; i < 100000 ; i++ )
hofstadters[ i - 1 ] = hofstadters[ i - 1 - hofstadters[ i - 1 - 1 ]] +
hofstadters[ i - 1 - hofstadters[ i - 2 - 1 ]] ;
std::cout << "The first 10 numbers are:\n" ;
for ( int i = 0 ; i < 10 ; i++ )
std::cout << hofstadters[ i ] << std::endl ;
std::cout << "The 1000'th term is " << hofstadters[ 999 ] << " !" << std::endl ;
int less_than_preceding = 0 ;
for ( int i = 0 ; i < 99999 ; i++ ) {
if ( hofstadters[ i + 1 ] < hofstadters[ i ] )
less_than_preceding++ ;
}
std::cout << less_than_preceding << " times a number was preceded by a greater number!\n" ;
return 0 ;
}

Output:
The first 10 numbers are:
1
1
2
3
3
4
5
5
6
6
The 1000'th term is 502 !
49798 times a number was preceded by a greater number!

SOURCE

Content is available under GNU Free Documentation License 1.2.