>>2
Ok, try to beat this: O(n) in time. I don't think you can make it consume much less than O(n) memory or I'll be curious to know how. I'm sure the program can be much shorter in another language.
int main(int argc, char *argv[])
{
int n = atol(argv[1]); unsigned long R[n]; R[0] = 1;
if (n > 1) {
R[1] = 3; int S = 2; int P = 1;
for (int i = 1; i < n; i++) {
R[i] = R[i - 1] + S;
++S == R[P] && S++;
R[P] < S && P++;
}
}
for (int i = 0; i < n; i++) {
printf("%lu\n", R[i]);
}
}It outputs the Hofstadter sequence like this:
./a.out 20
1
3
7
12
18
26
35
45
56
69
83
98
114
131
150
170
191
213
236
260