C++: Hofstadter Q Sequence

Posted on September 1, 2017April 1, 2018 by TFE Times

Bjarne-stroustrup

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.

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.

Related