// collatz.mjs: the engine behind /strata/collatz/. The page runs these exact bytes in
// your browser, and verify-collatz.mjs imports this same file and checks every function
// against a second, deliberately naive implementation. No dependencies.
//
// Two maps appear throughout, and the page always says which one it is counting:
//   C(n) = n/2 if n is even, 3n+1 if n is odd              (the "hailstone" steps)
//   T(n) = n/2 if n is even, (3n+1)/2 if n is odd          (the shortcut: 3n+1 is always
//                                                            even, so do the halving too)
// Everything below is exact integer arithmetic (BigInt where a number can grow).

// ── 1. the machine ──────────────────────────────────────────────────────────
// Run C from n until it reaches 1 (or a step cap). Returns the whole path.
export function hailstone(n, cap = 100000) {
  let x = BigInt(n);
  if (x < 1n) throw new Error('start must be a positive whole number');
  const path = [x];
  let peak = x, odd = 0;
  while (x !== 1n && path.length <= cap) {
    if (x & 1n) { x = 3n * x + 1n; odd++; } else x >>= 1n;
    path.push(x);
    if (x > peak) peak = x;
  }
  return { path, steps: path.length - 1, peak, odd, even: path.length - 1 - odd, reached: x === 1n };
}

// Stopping time under C: the first step at which the orbit falls below where it started.
export function stoppingTime(n) {
  const s = BigInt(n); let x = s, k = 0;
  if (s <= 1n) return 0;
  while (x >= s) { x = (x & 1n) ? 3n * x + 1n : x >> 1n; k++; }
  return k;
}

// ── 2. the last k bits decide the first k moves (Terras 1976) ───────────────
// The parity vector of n under T: bit i is 1 when T^i(n) is odd.
export function parityVector(n, k) {
  let x = BigInt(n); const v = [];
  for (let i = 0; i < k; i++) { const b = Number(x & 1n); v.push(b); x = b ? (3n * x + 1n) >> 1n : x >> 1n; }
  return v;
}

// For every residue r mod 2^k, its parity vector (as an integer, bit i = step i).
// Terras: this is a bijection onto all 2^k vectors. We return the vectors and let the
// caller count; nothing here assumes the theorem.
export function parityTable(k) {
  const N = 1 << k, out = new Uint32Array(N);
  for (let r = 0; r < N; r++) {
    // Any member of the class will do; use r + 2^k so that r = 0 is not the fixed point 0.
    const v = parityVector(BigInt(r + N), k);
    let w = 0; for (let i = 0; i < k; i++) w |= v[i] << i;
    out[r] = w >>> 0;
  }
  return out;
}

// After i steps of T along a parity vector with j ones so far,
//   T^i(n) = (3^j * n + c) / 2^i,  with c built by c <- 3c + 2^i at each odd step.
// So T^i(n) < n exactly when n * (2^i - 3^j) > c. Once 3^j < 2^i the whole residue class
// drops below its start, except for members smaller than c / (2^i - 3^j).
// dropsWithin(v, k) returns the first such i (or 0 if none within k), with the bound.
export function dropsWithin(v, k) {
  let j = 0n, c = 0n, p3 = 1n, p2 = 1n;
  for (let i = 0; i < k; i++) {
    if (v[i]) { c = 3n * c + p2; p3 *= 3n; j++; }
    p2 *= 2n;
    if (p3 < p2) return { at: i + 1, bound: c / (p2 - p3) };
  }
  return { at: 0, bound: null };
}

// Survivors: how many of the 2^k parity vectors (equivalently, by Terras, residues mod
// 2^k) have NOT yet been forced below their start within k steps, i.e. 3^(j_i) > 2^i
// for every prefix i <= k. Only the running count of ones matters, so this is a small
// dynamic program and runs to k in the hundreds. Returns BigInt counts for 1..K.
export function survivorCounts(K) {
  const L2 = Math.log2(3);
  let row = new Map([[0, 1n]]);   // ones-so-far -> number of vectors still alive
  const out = [];
  for (let i = 1; i <= K; i++) {
    const next = new Map();
    for (const [j, cnt] of row) {
      for (const b of [0, 1]) {
        const jj = j + b;
        // alive while 3^jj > 2^i; decide exactly with BigInt when the floats are close
        const d = jj * L2 - i;
        const alive = Math.abs(d) > 1e-9 ? d > 0 : 3n ** BigInt(jj) > 2n ** BigInt(i);
        if (alive) next.set(jj, (next.get(jj) || 0n) + cnt);
      }
    }
    row = next;
    let s = 0n; for (const c of row.values()) s += c;
    out.push(s);
  }
  return out;
}

// ── 3. change one number ────────────────────────────────────────────────────
// The generalised step: n/2 if even, q*n + r if odd. q=3,r=1 is Collatz; q=3,r=-1 on the
// positives is exactly Collatz on the negatives (n -> -n swaps them); q=5,r=1 is the 5x+1
// problem. Runs until the orbit repeats a value (a cycle) or passes `ceiling` (an escape:
// we stopped watching, which is NOT a proof that it never comes back).
export function orbitOf(n, q, r, ceiling = 10n ** 30n, cap = 200000) {
  let x = BigInt(n); const seen = new Map(); const path = [];
  const Q = BigInt(q), R = BigInt(r);
  while (path.length < cap) {
    if (seen.has(x)) {
      const loop = path.slice(seen.get(x));
      const min = loop.reduce((a, b) => (b < a ? b : a)), at = loop.indexOf(min);
      // print every loop from its smallest member, whichever start found it
      return { kind: 'cycle', path, cycle: [...loop.slice(at), ...loop.slice(0, at)], min };
    }
    if (x > ceiling) return { kind: 'escaped', path };
    seen.set(x, path.length); path.push(x);
    x = (x & 1n) ? Q * x + R : x >> 1n;
  }
  return { kind: 'capped', path };
}

// Classify every start 1..N under one rule. Cycles are keyed by their smallest member.
export function census(N, q, r, ceiling = 10n ** 30n) {
  const cycles = new Map(); const escaped = []; let capped = 0;
  const into = new Map();   // start value (Number) -> cycle key, memoised along paths
  for (let s = 1; s <= N; s++) {
    const o = orbitOf(s, q, r, ceiling);
    if (o.kind === 'cycle') {
      const key = o.min.toString();
      if (!cycles.has(key)) cycles.set(key, { min: o.min, cycle: o.cycle, count: 0 });
      cycles.get(key).count++;
      into.set(s, key);
    } else if (o.kind === 'escaped') escaped.push(s);
    else capped++;
  }
  return { cycles: [...cycles.values()].sort((a, b) => (a.min < b.min ? -1 : 1)), escaped, capped };
}

// Average drift of log(x) per T-step if parities were fair coin flips:
// half the steps multiply by q/2 (odd: (qn+1)/2), half by 1/2. So (1/2)ln(q/4).
export const drift = (q) => 0.5 * Math.log(q / 4);

// ── 4. every loop of length k, checked ──────────────────────────────────────
// A cycle of T of length k with j odd steps and parity vector v must satisfy
//   n = c(v) / (2^k - 3^j)
// (put T^k(n) = n in the formula above). Conversely, for EVERY 0/1 vector v that
// fraction is the unique 2-adic number whose parity vector is v repeated forever, so v
// belongs to a real cycle of whole numbers exactly when 2^k - 3^j divides c(v).
// We test every vector of length k with exact BigInt arithmetic, and report the whole-
// number solutions, positive and negative. `onProgress` is optional.
export function cyclesOfLength(k) {
  const found = [];
  const p2k = 2n ** BigInt(k);
  const N = 2 ** k;
  for (let w = 0; w < N; w++) {
    let c = 0n, j = 0, p2 = 1n;
    for (let i = 0; i < k; i++) {
      if ((w >>> i) & 1) { c = 3n * c + p2; j++; }
      p2 *= 2n;
    }
    const D = p2k - 3n ** BigInt(j);
    if (D !== 0n && c % D === 0n) found.push({ w, j, n: c / D });
  }
  return found;
}

// Group whole-number solutions into cycles: a cycle of period p shows up once for each
// of its p rotations, at every length k that is a multiple of p.
export function distinctCycles(solutions) {
  const orbits = new Map();
  for (const { n } of solutions) {
    const cyc = []; let x = n;
    do { cyc.push(x); x = (x & 1n) ? (3n * x + 1n) / 2n : x / 2n;
         // BigInt division truncates toward zero; for negative odd x, 3x+1 is even so /2 is exact
    } while (x !== n && cyc.length < 10000);
    const min = cyc.reduce((a, b) => (b < a ? b : a));
    // show each loop starting from its member nearest zero, so every rotation prints alike
    const abs = (v) => (v < 0n ? -v : v);
    let s = 0; cyc.forEach((v, i) => { if (abs(v) < abs(cyc[s])) s = i; });
    orbits.set(min.toString(), { min, period: cyc.length, members: [...cyc.slice(s), ...cyc.slice(0, s)] });
  }
  return [...orbits.values()].sort((a, b) => (a.min < b.min ? -1 : 1));
}
