C++: Hofstadter-Conway $10,000 Sequence

The definition of the sequence is colloquially described as:

Starting with the list [1,1],
Take the last number in the list so far: 1, I’ll call it x.
Count forward x places from the beginning of the list to find the first number to add (1)
Count backward x places from the end of the list to find the second number to add (1)
Add the two indexed numbers from the list and the result becomes the next number in the list (1+1)
This would then produce [1,1,2] where 2 is the third element of the sequence.

Note that indexing for the description above starts from alternately the left and right ends of the list and starts from an index of one.

A less wordy description of the sequence is:

   a(1)=a(2)=1
   a(n)=a(a(n-1))+a(n-a(n-1))

The sequence begins:

   1, 1, 2, 2, 3, 4, 4, 4, 5, ...

Interesting features of the sequence are that:

a(n)/n tends to 0.5 as n grows towards infinity.
a(n)/n where n is a power of 2 is 0.5
For n>4 the maximal value of a(n)/n between successive powers of 2 decreases.

The sequence is so named because John Conway offered a prize of $10,000 to the first person who could find the first position, p in the sequence where

   |a(n)/n| < 0.55 for all n > p.

It was later found that Hofstadter had also done prior work on the sequence.

The ‘prize’ was won quite quickly by Dr. Colin L. Mallows who proved the properties of the sequence and allowed him to find the value of n. (Which is much smaller than the 3,173,375,556. quoted in the NYT article)
The task is to:

Create a routine to generate members of the Hofstadter-Conway $10,000 sequence.
Use it to show the maxima of a(n)/n between successive powers of two up to 2**20
As a stretch goal: Compute the value of n that would have won the prize and confirm it is true for n up to 2**20

#include <deque>
#include <iostream>

int hcseq(int n)
{
	static std::deque<int> seq(2, 1);
	while (seq.size() < n)
	{
		int x = seq.back();
		seq.push_back(seq[x-1] + seq[seq.size()-x]);
	}
	return seq[n-1];
}

int main()
{
	int pow2 = 1;
	for (int i = 0; i < 20; ++i)
	{
		int pow2next = 2*pow2;
		double max = 0;
		for (int n = pow2; n < pow2next; ++n)
		{
			double anon = hcseq(n)/double(n);
			if (anon > max)
			max = anon;
		}
		std::cout << "maximum of a(n)/n between 2^" << i
		<< " (" << pow2 << ") and 2^" << i+1
		<< " (" << pow2next << ") is " << max << "\n";
		pow2 = pow2next;
	}
}

Output:

maximum of a(n)/n between 2^0 (1) and 2^1 (2) is 1
maximum of a(n)/n between 2^1 (2) and 2^2 (4) is 0.666667
maximum of a(n)/n between 2^2 (4) and 2^3 (8) is 0.666667
maximum of a(n)/n between 2^3 (8) and 2^4 (16) is 0.636364
maximum of a(n)/n between 2^4 (16) and 2^5 (32) is 0.608696
maximum of a(n)/n between 2^5 (32) and 2^6 (64) is 0.590909
maximum of a(n)/n between 2^6 (64) and 2^7 (128) is 0.576087
maximum of a(n)/n between 2^7 (128) and 2^8 (256) is 0.567416
maximum of a(n)/n between 2^8 (256) and 2^9 (512) is 0.559459
maximum of a(n)/n between 2^9 (512) and 2^10 (1024) is 0.554937
maximum of a(n)/n between 2^10 (1024) and 2^11 (2048) is 0.550101
maximum of a(n)/n between 2^11 (2048) and 2^12 (4096) is 0.547463
maximum of a(n)/n between 2^12 (4096) and 2^13 (8192) is 0.544145
maximum of a(n)/n between 2^13 (8192) and 2^14 (16384) is 0.542443
maximum of a(n)/n between 2^14 (16384) and 2^15 (32768) is 0.540071
maximum of a(n)/n between 2^15 (32768) and 2^16 (65536) is 0.538784
maximum of a(n)/n between 2^16 (65536) and 2^17 (131072) is 0.537044
maximum of a(n)/n between 2^17 (131072) and 2^18 (262144) is 0.53602
maximum of a(n)/n between 2^18 (262144) and 2^19 (524288) is 0.534645
maximum of a(n)/n between 2^19 (524288) and 2^20 (1048576) is 0.533779

SOURCE

Content is available under GNU Free Documentation License 1.2.