docker_space/frontier_cs_7/analysis.py

# Check which free chain nodes are actually needed
L, R = 577837, 979141
lenL = L.bit_length()
lenR = R.bit_length()

# The recursive decomposition
needed_free = set()
range_nodes = {}

def gr(k, lo, hi):
    if lo > hi:
        return None
    if k == 0:
        return ('END',) if (lo == 0 and hi == 0) else None
    if lo == 0 and hi == (1 << k) - 1:
        needed_free.add(k)
        return ('FREE', k)
    
    key = (k, lo, hi)
    if key in range_nodes:
        return range_nodes[key]
    
    mid = 1 << (k-1)
    left = None
    if lo <= min(hi, mid-1):
        left = gr(k-1, lo, min(hi, mid-1))
    right = None
    if max(lo, mid) <= hi:
        right = gr(k-1, max(lo, mid) - mid, hi - mid)
    
    if left is None and right is None:
        range_nodes[key] = None
        return None
    
    range_nodes[key] = ('RANGE', k, lo, hi, left, right)
    return range_nodes[key]

for length in range(lenL, lenR+1):
    rs = 1 << (length-1)
    re = (1 << length) - 1
    cL = max(L, rs)
    cR = min(R, re)
    if cL > cR:
        continue
    if length == 1:
        pass  # END
    else:
        gr(length-1, cL - rs, cR - rs)

print("Directly referenced free nodes:", sorted(needed_free))
print("Total needed free chain nodes (including intermediate):", end=" ")

# All free nodes needed: for each directly referenced F[k], we need F[1]..F[k]
all_free = set()
for k in needed_free:
    for i in range(1, k+1):
        all_free.add(i)
print(sorted(all_free))
print(f"Free chain size: {len(all_free)}")

# Count range nodes
rn = sum(1 for v in range_nodes.values() if v is not None)
print(f"Range nodes: {rn}")
print(f"Total: 2 (START+END) + {len(all_free)} (free) + {rn} (range) = {2 + len(all_free) + rn}")