Collatz sequences meet at a point

Question

I was solving the problem,in which we are given two starting values of collatz sequence and our task is to say after how many steps their sequences “meet” for the first time. For ex - a= 7 , b= 8
a = 7 -> 22 -> 11 -> .... -> 5 -> 16 -> 8
b = 8

So the collatz sequence starting with 7 will meet the other sequence at 8 .

I tried a normal approach but it's not optimized . Can anyone give good optimize approach ?

Constraints : 1<=a<=b<=10^6

Answer 1

This is what I'd do. In case of many repeated queries, preparing a table "first term of Collatz sequence below starting value $n$" for $n=2,3,\ldots, 10^6$ may speed up things.

Assume $b>a$. Compute the Collatz sequence starting with $b$ until the first time the sequence reaches some $b'<b$.

• If $b'>a$, scratch the $b$-sequence, let $b\leftarrow b'$, and create the $b$-sequence again up to a new $b'<b$.
• If $b'=a$, the answer is $a$, and we are done.

Otherwise, compute the sequence starting at $a$ until you reach $a'<a$. If $b'=a'$, follow both sequences back step by step until you reach the point they meet, and we are done. Otherwise, let $b=\max\{a',b'\}$, $a=\min\{a',b'\}$ and restart.

---

Then again, the maximal sequence length with starting values $\le 10^6$ is 524, so simply computing the two sequences to the end and looking for the meeting point from their ends cannot take too long ...