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.

Task

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 1000^{th} term is: 502

#include <iostream>intmain( ) {
int hofstadters[100000] ;
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" ;
return0 ;
}

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!