fbpx

C++: Hofstadter Q Sequence

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 1000th 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!

SOURCE

Content is available under GNU Free Documentation License 1.2.

Our team found a curious site for our readers that are fans of online gaming, a rather exciting site that provides the latest gaming technology. Casinodots.com is the site, they compile the best reviews of MGA casino utan svensk licens sites. This site might pique your curiosity and you can win extra money!