"""parity.py -- exact verification of the parity sieve (Lemma lem:parity) and its
corollary: <prod sigma_{q_i}^{e_i}> = 0 whenever sum of e_i over even q_i is odd.
Checks all clauses on explicit multisets in exact rational arithmetic, including
the sharpness examples quoted in the paper.
"""
from fractions import Fraction as F
from math import gcd, lcm

def mu(n):
    if n == 1: return 1
    r, m, p = 1, n, 2
    while p * p <= m:
        if m % p == 0:
            m //= p
            if m % p == 0: return 0
            r = -r
        p += 1
    if m > 1: r = -r
    return r

SV = {}
def sig(q):
    if q in SV: return SV[q]
    out = []
    for j in range(q):
        x = F(2 * j + 1, 2); v = F(0)
        for t in range(1, q + 1):
            if q % t == 0 and mu(t) != 0:
                y = F(t) * x / q
                v += F(mu(t), t) * (y - (y.numerator // y.denominator) - F(1, 2))
        out.append(v)
    SV[q] = out
    return out

def gmean(spec):
    """exact <prod sigma_q^e> over the common period"""
    L = lcm(*[q for q, e in spec])
    tot = F(0)
    for n in range(L):
        p = F(1)
        for q, e in spec: p *= sig(q)[n % q] ** e
        tot += p
    return tot / L

def even_slots(spec):
    return sum(e for q, e in spec if q % 2 == 0)

CASES = [
    # (3,1) sector: q even, r odd dies; q even, r even lives
    [(6,3),(3,1)], [(6,3),(2,1)], [(10,3),(5,1)], [(10,3),(2,1)],
    [(30,3),(15,1)], [(30,3),(6,1)], [(42,3),(21,1)], [(42,3),(6,1)],
    # (2,1,1): r !≡ s (mod 2) dies; same parity lives
    [(6,2),(10,1),(15,1)], [(42,2),(10,1),(15,1)], [(30,2),(10,1),(15,1)],
    [(2,2),(3,1),(6,1)], [(15,2),(21,1),(35,1)], [(5,2),(3,1),(15,1)],
    [(30,2),(3,1),(5,1)], [(15,2),(6,1),(10,1)], [(30,2),(2,1),(6,1)],
    # (1,1,1,1): odd number of even conductors dies
    [(2,1),(6,1),(10,1),(15,1)], [(2,1),(6,1),(10,1),(30,1)],
    [(3,1),(6,1),(10,1),(15,1)], [(6,1),(10,1),(15,1),(30,1)],
]
ok = True
for spec in CASES:
    m = gmean(spec)
    pred_zero = even_slots(spec) % 2 == 1
    status = "OK" if (pred_zero == (m == 0)) or (not pred_zero) else "VIOLATION"
    if pred_zero and m != 0: ok = False; status = "VIOLATION"
    print(f"{str(spec):42s} even-slots={even_slots(spec)}  mean={m}  {status}")
print("ALL PARITY PREDICTIONS HOLD" if ok else "PARITY VIOLATION FOUND")