Which pairs can go on infinitely?

Question

Given a pair of different integers $a$ and $b$ and operation: $$(a,b) \rightarrow \begin{cases} (a-b,2b), &\text{for}\; a>b \\ (2a,b-a), &\text{for}\; b>a \\ \text{stop}, &\text{for}\; a=b \end{cases}$$

After enough repetitions, some integers, like 7 and 9 become equal to each other, causing the loop to stop :

a	b
7	9
14	2
12	4
8	8

Others, such as $1$ and $21$ don't :

a	b
1	21
2	20
4	18
8	14
16	6
10	12
20	2

My question is how to determine (without going through the process), whether the two numbers will go on ad infinitum or stop after some loops.

This problem is part of a programming exercise I received from my mentor. I'm having trouble coming up with anything sensible to try. So far I've been banging my head against the proverbial wall by looking at what the sums, differences and ratios look like in pairs which go on forever and those which don't. Obviously, if the sum is odd, then it never stops, but otherwise I don't have anything solid.

To clarify, what happens when b>a: the operation is mirrored. The lesser number always doubles, and the greater number is always reduced by the prior lesser number. A pair is only stopped when a=b.

Answer 1

Given an arbitrary initial state, it's hard to tell if it will end at a final state. But if we inverse the problem, we definitely know what the final state is, if there is one.

Assuming the final state is $(2x,2x)$. Then the previous state must be $(x,3x)$ or $(3x,x)$. Since they are symmetric, let's just use $(x,3x)$. There are two possible previous states of that, $(x/2,7x/2)$ and $(5x/2,3x/2)$. It's easier to just write their ratio. Let's write the ratio of them starting from the final state, and then the possible previous states:

                    1:1
                    1:3
           1:7                 3:5
    1:15        9:7      3:13        11:5
1:31 17:15  9:23 25:7  3:29 19:13  11:21 27:5

At this point, it's obvious: The ratio is always $p:q$ such that $p+q=2^n$. The proof is not hard.

So, we just find the $gcd(a,b)$ and divide it to find their ratio $a:b=p:q$ in irreducible form, and if $p+q$ is a power of 2, it will end.

(PS: I assumed that $a$ and $b$ must be positive, but you didn't actually specify that. So, if they can be non-positive, then there's another possibility such that it never ends: $a\leq 0$ or $b\leq 0$ and $a\neq b$, since the smaller number (negative or zero) will always be doubled.)

(The proof:

Suppose the current numbers in the ratios are $k:2^n-k$, where $k=1,3,5,...,2^{\frac{n}{2}}-1$.

The two possible previous ratios for the ratio $k:2^n-k$ are:

$k:2(2^n-k)+k$ and $2k+(2^n-k):2^n-k$

simplify and we get $k:2^{n+1}-k$ and $2^n+k:2^n-k$

The smaller number of the first ratio covers the $k$ that goes from 1 to $2^\frac{n}{2}-1$, that of the second ratio, $2^n-k$, covers the rest of it, $2^\frac{n}{2}+1$ to $2^n-1$. The summation is always $2^{n+1}$. The proof is complete by induction.)