// ── Deep scales in Z_n: the full verified computation ─────────────────────────
//
// A scale is a subset S ⊆ Z_n with |S| ≥ 2. Its INTERVAL-CLASS VECTOR is
//   ic[d] = #{ unordered {x,y} ⊆ S : (x−y) ≡ ±d (mod n) },   d = 1 .. ⌊n/2⌋.
// S is DEEP iff the ⌊n/2⌋ entries of ic are pairwise distinct — "each interval
// class occurs a unique number of times" (Winograd 1966, unpub.; Gamer, "Some
// Combinational Resources of Equal-Tempered Systems", J. Music Theory 11/1 (1967)
// 32–59). The textbook example is the diatonic major scale {0,2,4,5,7,9,11} ⊂ Z_12,
// ic = ⟨2,5,4,3,6,1⟩ — a permutation of 1..6.
//
// Everything below is computed exactly (integer bitmasks) and asserted. The interval
// vector is built by two algorithms in three implementations, and all three must
// agree on every deep set: Method 1 is a direct pair-difference scan; Methods 2 and 3
// both compute the circular autocorrelation (bitwise popcount vs explicit sum), so
// they are two codings of one algorithm, not independent methods. A fourth lens
// (common-tone counts under transposition) is tied to ic exactly.
//
// The script also READS the committed b-files (bfile-*.txt here and the staged
// oversight/oeis/deep-scales/b-file-*.txt) and rechecks every term against the
// freshly computed counts; see the b-file comparison section near the end.
//
// Run:  node verify.mjs [NMAX]              (default 26, the staged b-file range)
//       node verify.mjs 26 --bfile A        (write bfile-A.txt; or C, D)

import { writeFileSync, readFileSync, existsSync } from 'node:fs';
import { fileURLToPath } from 'node:url';
import { dirname } from 'node:path';
const __dirname = dirname(fileURLToPath(import.meta.url));

let CHK = 0, FAIL = 0;
const eq = (a, b, m) => { CHK++; const ok = JSON.stringify(a) === JSON.stringify(b);
  if (!ok) { FAIL++; console.error('MISMATCH', m, a, b); } return ok; };
const T = (c, m) => { CHK++; if (!c) { FAIL++; console.error('FAIL:', m); } };

function popcount(x){ x=x-((x>>>1)&0x55555555); x=(x&0x33333333)+((x>>>2)&0x33333333);
  x=(x+(x>>>4))&0x0f0f0f0f; return (x*0x01010101)>>>24; }
function rot(mask,r,n){ const lo = mask>>>(n-r); return ((mask<<r)|lo) & ((1<<n)-1); }

// Method 1 — direct: scan every pair of pitches.
function icDirect(mask,n){ const m=Math.floor(n/2); const v=new Array(m).fill(0);
  const S=[]; for(let i=0;i<n;i++) if(mask&(1<<i)) S.push(i);
  for(let i=0;i<S.length;i++) for(let j=i+1;j<S.length;j++){
    let d=((S[j]-S[i])%n+n)%n; if(d>n-d) d=n-d; v[d-1]++; } return v; }

// Method 2 — rotation/autocorrelation by popcount (the fast scanner).
function icRot(mask,n){ const m=Math.floor(n/2); const v=new Array(m).fill(0);
  for(let d=1;d<=m;d++){ let c=popcount(mask & rot(mask,d,n));
    if(n%2===0 && d===n/2) c=c/2; v[d-1]=c; } return v; }

// Method 3 — explicit circular autocorrelation a[d]=Σ_i s_i·s_{i+d}.
function icPoly(mask,n){ const s=[]; for(let i=0;i<n;i++) s.push((mask>>i)&1);
  const m=Math.floor(n/2); const v=new Array(m).fill(0);
  for(let d=1;d<=m;d++){ let c=0; for(let i=0;i<n;i++) c+=s[i]*s[(i+d)%n];
    if(n%2===0 && d===n/2) c/=2; v[d-1]=c; } return v; }

// Lens 4 — common tones under transposition: CT(t) = |S ∩ (S+t)|.
// For t<n/2 this equals ic[t]; at t=n/2 it equals 2·ic[n/2] (each shared pair
// counted from both ends). Ties Gamer's "distinct common-tone counts" view to ic.
function commonTones(mask,n,t){ return popcount(mask & rot(mask,t,n)); }

function distinct(a){ return new Set(a).size === a.length; }
function inv(mask,n){ let r=0; for(let i=0;i<n;i++) if(mask&(1<<i)) r|=1<<((n-i)%n); return r>>>0; }
function neck(mask,n){ let best=mask,r=mask; for(let k=1;k<n;k++){ r=rot(r,1,n); if(r<best) best=r; } return best>>>0; }
function neckDi(mask,n){ return Math.min(neck(mask,n), neck(inv(mask,n),n))>>>0; }
function isInvSym(mask,n){ const im=inv(mask,n); for(let k=0;k<n;k++) if(rot(im,k,n)===mask) return true; return false; }
// Generated (well-formed) scale: a transposition of an arithmetic progression {a,a+g,…,a+(k−1)g}.
function generator(mask,n){ const S=[]; for(let i=0;i<n;i++) if(mask&(1<<i)) S.push(i); const k=S.length;
  for(let g=1;g<n;g++) for(const a of S){ let m=0,x=a; for(let t=0;t<k;t++){ m|=1<<x; x=(x+g)%n; }
    if(m===mask) return g; } return 0; }
// coprime generator only (the "generated scale" of the classification theorem)
function gcd(a,b){ while(b){ [a,b]=[b,a%b]; } return a; }
function coprimeGen(mask,n){ const g=generator(mask,n); return (g && gcd(g,n)===1) ? g : 0; }
function phi(n){ let r=0; for(let k=1;k<=n;k++) if(gcd(k,n)===1) r++; return r; }
function cls(g,n){ let d=((g%n)+n)%n; return d>n-d ? n-d : d; }            // interval class of g
function period(mask,n){ for(let p=1;p<n;p++) if(n%p===0 && rot(mask,p,n)===mask) return p; return n; }

const NMAX = parseInt(process.argv[2]||'26',10);
const A=[], C=[], D=[]; const nonGen=[];
for(let n=1;n<=NMAX;n++){
  let a=0; const seenC=new Set(), seenD=new Set();
  const full=((1<<n)-1)>>>0;
  for(let mask=0;mask<=full;mask++){ if(popcount(mask)<2) continue;
    const v=icRot(mask,n); if(!distinct(v)) continue;
    a++; const kc=neck(mask,n); const isNew=!seenC.has(kc); seenC.add(kc); seenD.add(neckDi(mask,n));
    // two algorithms, three implementations: all must agree on every deep set
    eq(v, icDirect(mask,n), `icDirect n=${n} mask=${mask}`);
    eq(v, icPoly(mask,n),  `icPoly  n=${n} mask=${mask}`);
    // common tones tied to ic, exactly
    for(let t=1;t<=Math.floor(n/2);t++){
      const expect = (n%2===0 && t===n/2) ? 2*v[t-1] : v[t-1];
      T(commonTones(mask,n,t)===expect, `commonTones n=${n} mask=${mask} t=${t}`);
    }
    // structural: every deep set is inversionally symmetric
    T(isInvSym(mask,n), `deep-but-not-invSym n=${n} mask=${mask}`);
    // aperiodicity (n≥5) ⇒ each class has n transpositions ⇒ A(n)=n·C(n)
    if(n>=5) T(period(mask,n)===n, `deep-but-periodic n=${n} mask=${mask}`);
    // generator-recovery lemma: for a coprime-generated deep scale, the generator's
    // interval class is the UNIQUE maximum of ic (this is what forces C(n)=φ(n)).
    const cg=coprimeGen(mask,n);
    if(cg){ const mx=Math.max(...v); const arg=v.map((x,i)=>x===mx?i+1:0).filter(Boolean);
      T(arg.length===1 && arg[0]===cls(cg,n), `argmax(ic)≠cls(generator) n=${n} mask=${mask} g=${cg}`); }
    // classification (n≥7): every deep scale is coprime-generated, or the sporadic {0,1,2,4}⊂Z₆
    if(n>=7) T(cg!==0, `unclassified deep scale n=${n} mask=${mask} ic=${v}`);
    if(isNew && !generator(kc,n)){ const S=[]; for(let i=0;i<n;i++) if(kc&(1<<i)) S.push(i);
      nonGen.push(`n=${n}:{${S.join(',')}}`); }
  }
  A.push(a); C.push(seenC.size); D.push(seenD.size);
}

// the diatonic is deep with the textbook interval vector
eq(icDirect((1<<0)|(1<<2)|(1<<4)|(1<<5)|(1<<7)|(1<<9)|(1<<11),12), [2,5,4,3,6,1], 'diatonic ic-vector');
T(distinct([2,5,4,3,6,1]), 'diatonic is deep');
// C === D  (deep ⇒ inversionally symmetric, so transposition- and inversion-classes coincide)
for(let i=0;i<C.length;i++) T(C[i]===D[i], `C!=D at n=${i+1}`);
// prime structure: A(p)=p(p−1), C(p)=p−1 for primes p≥5
const isP=x=>{ if(x<2) return false; for(let d=2;d*d<=x;d++) if(x%d===0) return false; return true; };
for(let n=5;n<=NMAX;n++) if(isP(n)){ T(A[n-1]===n*(n-1), `A(${n})!=p(p-1)`); T(C[n-1]===n-1, `C(${n})!=p-1`); }

// THE CENSUS IDENTITY (this pass): C(n)=φ(n) and A(n)=n·φ(n) for n≥7 (and n=2,3,5);
// the only deviations are n∈{1,4,6}. See census-theorem.md for the proof.
for(let n=2;n<=NMAX;n++){ if(n===4||n===6) continue;
  T(C[n-1]===phi(n), `C(${n})=φ: ${C[n-1]} vs ${phi(n)}`);
  if(n>=5) T(A[n-1]===n*phi(n), `A(${n})=n·φ: ${A[n-1]} vs ${n*phi(n)}`);
}
if(NMAX>=4){ T(A[3]===11 && C[3]===4, `n=4 exception (A=11,C=4) got A=${A[3]},C=${C[3]}`); }
if(NMAX>=6){ T(A[5]===18 && C[5]===3, `n=6 exception (A=18,C=3; the sporadic) got A=${A[5]},C=${C[5]}`); }

// ── b-file comparison: READ the committed b-files and recheck every term ───────
// Reads both the research copies (bfile-*.txt, written by --bfile) and the staged
// oversight copies (b-file-*.txt), which have different filenames on purpose:
// this block is what guarantees the two never silently diverge, and that a short
// NMAX run can never pass while leaving staged terms unchecked (it is a FAILURE,
// not a skip, if a b-file holds terms beyond NMAX). This code only reads; the
// only writer is the explicit --bfile flag below.
function checkBfile(path, seq, name){
  if(!existsSync(path)){ console.log(`b-file ${name}: ${path} MISSING`); T(false, `b-file missing: ${path}`); return; }
  const rows = readFileSync(path,'utf8').split('\n')
    .map(l=>l.trim()).filter(l=>l && !l.startsWith('#'))
    .map(l=>l.split(/\s+/).map(Number));
  T(rows.length <= NMAX,
    `b-file ${name}: holds ${rows.length} terms but NMAX=${NMAX}; rerun with NMAX >= ${rows.length} to cover every staged term`);
  for(let i=0;i<rows.length;i++){
    const [idx,val]=rows[i];
    T(idx===i+1, `b-file ${name}: line ${i+1} index ${idx}, expected ${i+1}`);
    if(i<seq.length) T(val===seq[i], `b-file ${name}: term n=${idx} is ${val}, computed ${seq[i]}`);
  }
  const covered=Math.min(rows.length,seq.length);
  console.log(`b-file ${name}: ${rows.length} terms read, ${covered} checked term-for-term against this run`);
}
const STAGED = __dirname + '/../../oversight/oeis/deep-scales';
checkBfile(__dirname+'/bfile-A.txt', A, 'research A');
checkBfile(__dirname+'/bfile-C.txt', C, 'research C');
checkBfile(__dirname+'/bfile-D.txt', D, 'research D');
checkBfile(STAGED+'/b-file-A.txt', A, 'staged A');
checkBfile(STAGED+'/b-file-C.txt', C, 'staged C');

console.log('A — deep subsets of Z_n (|S|≥2), n=1..'+NMAX+':');
console.log('  '+A.join(', '));
console.log('C — deep scales up to transposition, n=1..'+NMAX+':');
console.log('  '+C.join(', '));
console.log('D — up to transposition + inversion:');
console.log('  '+D.join(', '));
console.log('φ(n)  for comparison:');
console.log('  '+Array.from({length:NMAX},(_,i)=>phi(i+1)).join(', '));
console.log('  ↳ C(n) = φ(n) for every n≥7 (and n=2,3,5); deviates only at n=4,6. A(n) = n·φ(n) likewise.');
console.log('non-generated ("sporadic") deep scales found: '+(nonGen.length?nonGen.join('  ')+'  — the unique sporadic, a published theorem (Demaine/Winograd/Clough)':'(none)'));
console.log(`\n${CHK} checks, ${FAIL} failures — ${FAIL ? '*** FAIL ***' : 'ALL PASS'}`);

// b-file export
if(process.argv.includes('--bfile')){
  const which=process.argv[process.argv.indexOf('--bfile')+1]||'A';
  const seq = which==='C' ? C : (which==='D' ? D : A);
  const label = which==='A'?'deep subsets':which==='C'?'deep scales up to transposition':'deep scales up to transposition+inversion';
  const lines=['# deep scales in Z_n — '+label+'; a(n), offset n=1'];
  for(let i=0;i<seq.length;i++) lines.push((i+1)+' '+seq[i]);
  writeFileSync(__dirname+`/bfile-${which}.txt`, lines.join('\n')+'\n');
  console.error(`wrote bfile-${which}.txt (${seq.length} terms)`);
}
process.exit(FAIL?1:0);
