The Hofstadter Q sequence is defined as:

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> int main( ) { 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" ; 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!

Content is available under GNU Free Documentation License 1.2.