def traj(n):
    t=[n]
    while n!=1:
        n=n//2 if n%2==0 else 3*n+1; t.append(n)
    return t
def first_meet(a,b):
    ta=traj(a); sb={v:j for j,v in enumerate(traj(b))}
    for i,v in enumerate(ta):
        if v in sb: return v,i,sb[v]
    return None

# TEST: for GENUINE merges (both branches take >=1 step, so a true
# two-parent join, not one trajectory being a tail of the other),
# is the meet value always == 4 (mod 6)?
genuine=0; mod6=collections.Counter() if False else {}
import collections
mod6=collections.Counter()
viol=[]
for n in range(2,20000):
    v,i,j=first_meet(n,n+1)
    if i>0 and j>0:            # genuine two-branch merge
        genuine+=1
        mod6[v%6]+=1
        if v%6!=4: viol.append((n,v,i,j))
print("genuine two-branch merges (n<20000): %d"%genuine)
print("meet-value residues mod 6:", dict(mod6))
print("violations of (meet==4 mod 6):", len(viol), viol[:5])

# WHY: a genuine merge value v needs an EVEN predecessor 2v AND an ODD
# predecessor u with 3u+1=v. u=(v-1)/3 must be a positive ODD integer.
#   -> v == 1 (mod 3)  and  (v-1)/3 odd  ->  v-1 == 3 (mod 6) -> v==4 (mod6)
# quick check that every v==4(mod6) has an odd predecessor:
ok=all(((v-1)%3==0 and ((v-1)//3)%2==1) for v in range(4,600,6))
print("every v==4(mod6) has odd predecessor (v-1)/3: %s"%ok)