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); tb=traj(b)
    sb=set(tb)
    for i,v in enumerate(ta):
        if v in sb:
            j=tb.index(v)
            return v, i, j   # meet value, steps-from-a, steps-from-b
    return None

print("=== consecutive merges: n and n+1, where do they first meet? ===")
print(" n   meet@   a_steps b_steps  shared_tail")
for n in range(20,45):
    v,i,j=first_meet(n,n+1)
    tail=len(traj(v))-1
    print(" %3d  %5d    %3d    %3d      %3d"%(n,v,i,j,tail))

# PREDICTION TEST: equal stopping time <=> meet with i==j (aligned merge)
def stop(n):
    s=0
    while n!=1: n=n//2 if n%2==0 else 3*n+1; s+=1
    return s
print("\n=== does equal stopping-time imply aligned meet (i==j)? ===")
eq=0; aligned=0
for n in range(2,2000):
    if stop(n)==stop(n+1):
        eq+=1
        v,i,j=first_meet(n,n+1)
        if i==j: aligned+=1
print("consecutive pairs with equal stopping time (n<2000): %d"%eq)
print("of those, meet with i==j (perfectly aligned tails): %d"%aligned)

# SCALE: how common is a long shared tail? distribution of (i and j) small
print("\n=== how FAST do neighbors merge? steps-to-meet for n..n+1, n<5000 ===")
import collections
c=collections.Counter()
for n in range(2,5000):
    v,i,j=first_meet(n,n+1)
    c[max(i,j)]+=1
for k in sorted(c)[:12]:
    print("  meet within %2d steps: %4d pairs"%(k,c[k]))