Problem Statement

The definition of the sequence is colloquially described as: 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: The sequence begins: Interesting features of the sequence are that:

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 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).

Let's start with the solution:

import std.stdio, std.algorithm;

void hofstadterConwaySequence(in int m) {
    auto alist = new int[m + 1];
    alist[0 .. 2] = 1;
    auto v = alist[2];
    int k1 = 2, lg2 = 1;
    double amax = 0.0;

    foreach (n; 2 .. m + 1) {
        v = alist[n] = alist[v] + alist[n - v];
        amax = max(amax, v * 1.0 / n);
        if ((k1 & n) == 0) {
            writefln("Max in [2^%d, 2^%d]: %f", lg2, lg2 + 1, amax);
            amax = 0;
            lg2++;
        }
        k1 = n;
    }
}

void main() {
    hofstadterConwaySequence(2 ^^ 20);
}