# The proof engine, checked exactly: along ONE doubling ray, the branch
# nodes (v==4 mod 6) have 3-adic residues that cycle through EVERY
# admissible class. Claim: 4 = 2^2 generates exactly the subgroup
# {x in (Z/3^k)* : x == 1 mod 3}, which has order 3^(k-1). Because 2
# is a primitive root mod 3^k, its square 4 generates the index-2
# subgroup, and that subgroup IS the units == 1 mod 3.
def subgroup(a,m):
    s=set(); x=1
    for _ in range(m):
        s.add(x); x=(x*a)%m
        if x==1: break
    return s
for k in range(1,8):
    m=3**k
    G4=subgroup(4,m)
    target={x for x in range(1,m) if x%3==1}   # units == 1 mod 3
    print("3^%d: |<4>|=%-6d  3^(k-1)=%-6d  <4>=={units==1 mod3}: %s"%(
        k, len(G4), 3**(k-1), G4==target))

# And the consequence, checked on a real ray: take a doubling ray from
# an odd seed, list its branch nodes' residues mod 2*3^k, confirm each
# admissible class hit equally over one full period.
import collections
k=3; M=2*3**k
# a doubling ray from seed u (odd, coprime to 3): u, 2u, 4u, ...
u=5
res=collections.Counter()
x=u
period=2*(2*3**(k-1))   # 2x the mult order to cover parity+3adic
for _ in range(period*3):
    if x%6==4: res[x%M]+=1
    x*=2
classes=[r for r in range(M) if r%6==4]
counts=[res[c] for c in classes]
print("\none doubling ray from seed",u,"- branch residues mod",M,":")
print("  classes:",classes)
print("  counts :",counts,"-> all equal:",len(set(counts))==1)