#!/usr/bin/env node
// The Josephus problem — offline verifier.
//
// n people stand in a circle, seats numbered 1..n. Counting starts at seat 1
// (seat 1 is "one"). Every k-th counted person is removed; counting resumes at
// the next living seat and wraps around. One seat is left standing: J(n,k).
//
// This file is the ground truth. The browser page at
// public/strata/the-count-that-spared-him/index.html recomputes the SAME numbers
// live (same convention, same seeds) and must match this output digit for digit.
//
// Everything here is exact integer arithmetic on small integers (< 2^21), so no
// BigInt is needed and no floating point enters a claim.
//
// Run: node research/josephus/verify.mjs

'use strict';

let CHECKS = 0, PASS = 0;
function check(name, cond, detail) {
  CHECKS++;
  if (cond) { PASS++; console.log(`  ✓ ${name}${detail ? ' — ' + detail : ''}`); }
  else { console.log(`  ✗ ${name}${detail ? ' — ' + detail : ''}`); }
}

// ---------------------------------------------------------------------------
// Reference simulator — the definition itself, no cleverness.
// Removes every k-th living seat until `remain` seats are left; returns the
// survivors (1-indexed) in ascending order, plus the full elimination order.
// O(n * k) with an array; fine for the sizes we check the closed forms against.
// ---------------------------------------------------------------------------
function simulate(n, k, remain = 1) {
  const alive = [];
  for (let i = 1; i <= n; i++) alive.push(i);
  const removed = [];
  let idx = 0; // index into `alive` of the next seat to start counting FROM
  while (alive.length > remain) {
    // count k seats forward, starting the count at `idx`
    idx = (idx + k - 1) % alive.length;
    removed.push(alive[idx]);
    alive.splice(idx, 1);
    // after removal, `idx` now points at the seat that followed the removed one
    if (idx >= alive.length) idx = 0;
  }
  return { survivors: alive.slice().sort((a, b) => a - b), removed };
}

// Fast survivor for a single k=2 or general k via the O(n) recurrence.
// 0-indexed: j(1)=0, j(m) = (j(m-1)+k) mod m. Survivor (1-indexed) = j(n)+1.
function josephusRecur(n, k) {
  let j = 0;
  for (let m = 2; m <= n; m++) j = (j + k) % m;
  return j + 1;
}

// The closed form for k=2: n = 2^p + L with 0 <= L < 2^p  ->  J = 2L + 1.
function josephusTwoClosed(n) {
  let p = 1;
  while (p * 2 <= n) p *= 2; // largest power of two <= n
  const L = n - p;
  return 2 * L + 1;
}

// The bit trick for k=2: write n in binary, move the leading 1 to the tail.
// (A single-place cyclic left rotation of the b-bit representation.)
function rotateLeadingBit(n) {
  let b = 0, t = n;
  while (t > 0) { b++; t >>= 1; } // number of bits
  if (b === 0) return 0;
  const lead = 1 << (b - 1);
  const rest = n - lead;          // drop the leading 1
  return (rest << 1) | 1;         // shift up, append a 1 at the bottom
}

console.log('The Josephus problem — verification\n');

// ---------------------------------------------------------------------------
// Check 1 — k=2 closed form vs the definition (direct simulation).
// ---------------------------------------------------------------------------
{
  let ok = 0, N = 4000;
  for (let n = 1; n <= N; n++) {
    const sim = simulate(n, 2).survivors[0];
    if (sim === josephusTwoClosed(n)) ok++;
  }
  check('k=2 closed form 2L+1 matches the circle for every n in 1..4000',
    ok === N, `${ok}/${N}`);
}

// ---------------------------------------------------------------------------
// Check 2 — the bit-rotation trick equals the closed form, far out.
// ---------------------------------------------------------------------------
{
  let ok = 0, N = (1 << 20); // 1,048,576
  for (let n = 1; n <= N; n++) {
    if (rotateLeadingBit(n) === josephusTwoClosed(n)) ok++;
  }
  check('bit trick (rotate leading 1 to the tail) = 2L+1 for every n in 1..2^20',
    ok === N, `${ok}/${N}`);
}

// ---------------------------------------------------------------------------
// Check 3 — the doubling recurrence J(2n)=2J(n)-1, J(2n+1)=2J(n)+1.
// ---------------------------------------------------------------------------
{
  let ok = 0, N = 100000;
  for (let n = 1; n <= N; n++) {
    const jn = josephusTwoClosed(n);
    if (josephusTwoClosed(2 * n) === 2 * jn - 1 &&
        josephusTwoClosed(2 * n + 1) === 2 * jn + 1) ok++;
  }
  check('doubling recurrence holds for every n in 1..100000', ok === N, `${ok}/${N}`);
}

// ---------------------------------------------------------------------------
// Check 4 — general-k O(n) recurrence vs direct simulation.
// ---------------------------------------------------------------------------
{
  let ok = 0, total = 0;
  for (let k = 1; k <= 13; k++) {
    for (let n = 1; n <= 400; n++) {
      total++;
      if (josephusRecur(n, k) === simulate(n, k).survivors[0]) ok++;
    }
  }
  check('general-k recurrence (j=(j+k)%m) matches the circle over 13×400 (n,k) pairs',
    ok === total, `${ok}/${total}`);
}

// ---------------------------------------------------------------------------
// Check 5 — the legend, computed rather than asserted.
// 41 people, every 3rd removed, counting stops when TWO remain.
// The folklore says Josephus put himself and his friend where they would live.
// We do not trust the folklore's numbers; we compute them.
// ---------------------------------------------------------------------------
{
  const two = simulate(41, 3, 2).survivors;
  const one = simulate(41, 3, 1).survivors[0];
  // Report the computed positions; the page must show these same values.
  check('legend: 41 seats, every 3rd, last two standing are seats {16, 31}',
    two.length === 2 && two[0] === 16 && two[1] === 31, `computed {${two.join(', ')}}`);
  check('legend: 41 seats, every 3rd, single survivor is seat 31',
    one === 31, `computed ${one}`);
}

// ---------------------------------------------------------------------------
// Check 6 — cross-check against OEIS A006257 (the k=2 survivor sequence).
// The first 32 terms, transcribed from the OEIS listing.
// ---------------------------------------------------------------------------
{
  const A006257 = [1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1,
                   3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 1];
  let ok = 0;
  for (let i = 0; i < A006257.length; i++) {
    if (josephusTwoClosed(i + 1) === A006257[i]) ok++;
  }
  check('k=2 survivors reproduce OEIS A006257, terms 1..32',
    ok === A006257.length, `${ok}/${A006257.length}`);
}

// ---------------------------------------------------------------------------
// Emit the seed values the page pins itself to (so a drift shows up in review).
// ---------------------------------------------------------------------------
console.log('\nPinned seeds (the page displays these same numbers):');
console.log('  J(n,2) for n=1..16 : [' +
  Array.from({ length: 16 }, (_, i) => josephusTwoClosed(i + 1)).join(', ') + ']');
console.log('  J(13,2) = ' + josephusTwoClosed(13) +
  '   (13 = 1101b -> rotate -> 1011b = ' + rotateLeadingBit(13) + ')');
console.log('  J(100,2) = ' + josephusTwoClosed(100) +
  '   (100 = 64 + 36, so 2*36+1)');
console.log('  legend J(41,3) two survivors = {' +
  simulate(41, 3, 2).survivors.join(', ') + '}');

console.log(`\n${PASS}/${CHECKS} checks pass`);
process.exit(PASS === CHECKS ? 0 : 1);
