#!/usr/bin/env node
// Thue–Morse — offline verifier for "The Fairest Order".
// Every factual claim the page makes is recomputed here from scratch and asserted.
// Run: node research/thue-morse/verify.mjs
//
// What it proves, exactly (no floats where integers will do):
//   1. Three independent definitions of t(n) agree on a long prefix.
//   2. Prouhet's theorem (1851): partition {0..2^(m)-1} by Thue–Morse parity into
//      A (t=0) and B (t=1); the two halves have EQUAL sums of j-th powers for
//      j = 0,1,...,m-1, and the equality FIRST BREAKS at j = m. (BigInt-exact.)
//   3. The word is overlap-free and cube-free on a long prefix (exhaustive), and
//      is NOT square-free (squares exist) — the exact register that made Thue
//      (1912) build it.
//   4. The "fair order" payoff, stated honestly (no overclaim):
//      (a) the ±1 partial sums of the Thue–Morse order are bounded by 1 on a long
//          prefix — the counting balance that motivates everything;
//      (b) under ALTERNATION the first mover wins every adjacent pair, so the
//          money-lead is monotone non-decreasing and equals Σ(v_{2i-1}−v_{2i}) ≥ 0
//          (a closed form, verified) — the first player literally cannot lose;
//      (c) under Thue–Morse the final gap is far smaller, and over many random
//          descending pots TM is, on average, dramatically fairer than ABAB.
//      The deep turn-taking optimality is Cooper–Dutle (2013), cited, not reproven.

let pass = 0, fail = 0;
const eq = (got, want, msg) => {
  const ok = got === want || (typeof got === 'bigint' && got === BigInt(want));
  console.log(`${ok ? 'PASS' : 'FAIL'}  ${msg}` + (ok ? '' : `  (got ${got}, want ${want})`));
  ok ? pass++ : fail++;
};
const ok = (cond, msg) => { console.log(`${cond ? 'PASS' : 'FAIL'}  ${msg}`); cond ? pass++ : fail++; };

// ---------- 1. three definitions agree ----------
const N = 1 << 14; // 16384

// (a) parity of popcount
const popPar = (n) => { let p = 0; while (n) { p ^= 1; n &= n - 1; } return p; };

// (b) substitution 0 -> 01, 1 -> 10, iterated
function bySubstitution(len) {
  let s = [0];
  while (s.length < len) {
    const next = [];
    for (const c of s) { next.push(c, c ^ 1); }
    s = next;
  }
  return s.slice(0, len);
}

// (c) recurrence t(0)=0, t(2n)=t(n), t(2n+1)=1-t(n)
const tcache = [0];
function byRecurrence(n) {
  if (tcache[n] !== undefined) return tcache[n];
  const v = (n & 1) ? (1 - byRecurrence((n - 1) >> 1)) : byRecurrence(n >> 1);
  tcache[n] = v;
  return v;
}

const sub = bySubstitution(N);
let agreeAB = true, agreeAC = true;
for (let n = 0; n < N; n++) {
  if (popPar(n) !== sub[n]) agreeAB = false;
  if (popPar(n) !== byRecurrence(n)) agreeAC = false;
}
ok(agreeAB, `popcount-parity == substitution on first ${N}`);
ok(agreeAC, `popcount-parity == recurrence on first ${N}`);
// spot the canonical prefix
eq(sub.slice(0, 16).join(''), '0110100110010110', 'prefix t[0..15] = 0110100110010110');

// ---------- 2. Prouhet's theorem (BigInt-exact) ----------
// For block {0..2^m - 1}: equal power sums j = 0..m-1, breaks at j = m.
function prouhet(m) {
  const M = 1 << m;
  const A = [], B = [];
  for (let n = 0; n < M; n++) (popPar(n) ? B : A).push(BigInt(n));
  const powSum = (set, j) => set.reduce((s, x) => s + x ** BigInt(j), 0n);
  return { A, B, powSum };
}
for (let m = 1; m <= 10; m++) {
  const { A, B, powSum } = prouhet(m);
  eq(A.length, B.length, `m=${m}: |A| == |B| == 2^${m - 1}`);
  let allEqual = true;
  for (let j = 0; j <= m - 1; j++) if (powSum(A, j) !== powSum(B, j)) allEqual = false;
  ok(allEqual, `m=${m}: power sums A==B for j=0..${m - 1} (degree ${m - 1} multigrade)`);
  // the bound is tight: it must break at j = m
  ok(powSum(A, m) !== powSum(B, m), `m=${m}: power sums DIFFER at j=${m} (bound is tight)`);
}
// show one full multigrade in the open (m=3): A={0,3,5,6}, B={1,2,4,7}
{
  const { A, B } = prouhet(3);
  eq(A.join(','), '0,3,5,6', 'm=3: A (evil numbers) = {0,3,5,6}');
  eq(B.join(','), '1,2,4,7', 'm=3: B (odious numbers) = {1,2,4,7}');
  // 0+3+5+6 = 14 = 1+2+4+7 ; 0+9+25+36 = 70 = 1+4+16+49
  eq(0n + 3n + 5n + 6n, 14n, 'm=3 deg1: 0+3+5+6 = 14');
  eq(1n + 2n + 4n + 7n, 14n, 'm=3 deg1: 1+2+4+7 = 14');
  eq(0n + 9n + 25n + 36n, 70n, 'm=3 deg2: 0²+3²+5²+6² = 70');
  eq(1n + 4n + 16n + 49n, 70n, 'm=3 deg2: 1²+2²+4²+7² = 70');
  // and they part at cubes
  ok((0n + 27n + 125n + 216n) !== (1n + 8n + 64n + 343n), 'm=3 deg3: cubes differ (368 vs 416)');
  eq(0n + 27n + 125n + 216n, 368n, 'm=3 deg3: A cubes = 368');
  eq(1n + 8n + 64n + 343n, 416n, 'm=3 deg3: B cubes = 416');
}

// ---------- 3. powers / repetitions ----------
// A factor of length k*p with period p is a k-th power. Search the prefix.
const W = 4096;
const w = sub.slice(0, W);
function hasKthPower(k) {
  // returns smallest [start, period] of an exact k-th power, or null
  for (let p = 1; p * k <= W; p++) {
    for (let i = 0; i + k * p <= W; i++) {
      let periodic = true;
      for (let d = 0; d < (k - 1) * p && periodic; d++) {
        if (w[i + d] !== w[i + d + p]) periodic = false;
      }
      if (periodic) return [i, p];
    }
  }
  return null;
}
// overlap = a factor with period p and length 2p+1 (exponent > 2). None should exist.
function hasOverlap() {
  for (let p = 1; 2 * p + 1 <= W; p++) {
    for (let i = 0; i + 2 * p + 1 <= W; i++) {
      let periodic = true;
      for (let d = 0; d < p + 1 && periodic; d++) if (w[i + d] !== w[i + d + p]) periodic = false;
      if (periodic) return [i, p];
    }
  }
  return null;
}
const sq = hasKthPower(2);
const cube = hasKthPower(3);
const ov = hasOverlap();
ok(sq !== null, `squares EXIST on first ${W} (so not square-free): first at i=${sq && sq[0]}, period ${sq && sq[1]}`);
ok(cube === null, `cube-free on first ${W} (no exact cube)`);
ok(ov === null, `overlap-free on first ${W} (no factor of exponent > 2)`);
// the smallest square is "00" (t = 0,1,1,0,... -> "11" at index 1, period 1)
eq(sq[1], 1, 'smallest square has period 1 (a repeated letter)');

// ---------- 4. the fair-order payoff ----------
function thueMorseOrder(len) {
  let s = '0';
  while (s.length < len) s = s.split('').map(c => c + (c === '0' ? '1' : '0')).join('');
  return s.slice(0, len).split('').map(c => (c === '0' ? 'A' : 'B')).join('');
}
function altOrder(len) {
  return Array.from({ length: len }, (_, i) => (i % 2 ? 'B' : 'A')).join('');
}
// (a) ±1 partial sums of the TM order are bounded by 1 on a long prefix.
{
  const order = thueMorseOrder(1 << 16);
  let s = 0, maxAbs = 0;
  for (const c of order) { s += c === 'A' ? 1 : -1; if (Math.abs(s) > maxAbs) maxAbs = Math.abs(s); }
  eq(maxAbs, 1, `TM ±1 partial sums bounded by 1 on first ${1 << 16} turns`);
}
// Two players pick from a pot of values[i] (sorted DESC) under a turn order; each
// turn the current player greedily takes the most valuable remaining item.
function play(values, order) {
  let a = 0n, b = 0n;
  for (let i = 0; i < order.length; i++) {
    if (order[i] === 'A') a += values[i]; else b += values[i];
  }
  return a - b; // A minus B
}
const absB = (d) => (d < 0n ? -d : d);
// (b) under ALTERNATION the first mover wins every adjacent pair: diff = Σ(v_{2i-1}-v_{2i}).
for (const L of [4, 8, 16]) {
  const values = Array.from({ length: L }, (_, i) => 2n ** BigInt(L - 1 - i)); // binary pot, DESC
  let pairSum = 0n;
  for (let i = 0; i + 1 < L; i += 2) pairSum += values[i] - values[i + 1];
  const al = play(values, altOrder(L));
  eq(al, pairSum, `binary pot L=${L}: alternation diff == Σ(v_{2i-1}-v_{2i}) (first mover wins every pair)`);
  ok(al > 0n, `binary pot L=${L}: alternation diff > 0 (first player cannot lose)`);
  const tm = play(values, thueMorseOrder(L));
  ok(absB(tm) < al, `binary pot L=${L}: Thue–Morse gap (${absB(tm)}) < alternation gap (${al})`);
}
// the L=16 binary pot has the clean closed form (2^16-1)/3 = 21845 for alternation
eq(play(Array.from({ length: 16 }, (_, i) => 2n ** BigInt(15 - i)), altOrder(16)), 21845n,
  'binary pot L=16: alternation gap = (2^16-1)/3 = 21845 exactly');
// Random fair-ish check: over many random DESC value vectors, TM's |diff| is, on
// average, smaller than alternation's. (Stated as a tendency, computed honestly.)
{
  // deterministic PRNG (mulberry32) so the verifier is reproducible
  let seed = 0x9e3779b9 >>> 0;
  const rng = () => { seed |= 0; seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed); t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
  const L = 16, trials = 20000;
  let tmTot = 0, alTot = 0, tmWins = 0;
  for (let k = 0; k < trials; k++) {
    const vs = Array.from({ length: L }, () => BigInt(1 + Math.floor(rng() * 1000)));
    vs.sort((x, y) => (y > x ? 1 : y < x ? -1 : 0)); // DESC
    const t = absB(play(vs, thueMorseOrder(L)));
    const a = absB(play(vs, altOrder(L)));
    tmTot += Number(t); alTot += Number(a);
    if (t < a) tmWins++; else if (t === a) tmWins += 0.5;
  }
  ok(tmTot < alTot, `random DESC pots (L=16, ${trials} trials): mean |diff| TM (${(tmTot / trials).toFixed(2)}) < ALT (${(alTot / trials).toFixed(2)})`);
  ok(tmWins / trials > 0.5, `random DESC pots: TM at-least-as-fair fraction = ${(tmWins / trials * 100).toFixed(1)}%`);
}

console.log(`\n${pass}/${pass + fail} PASS${fail ? `  (${fail} FAIL)` : ''}`);
process.exit(fail ? 1 : 0);
