Algorithm for determining if two numbers form a loop

Question

My brute force algorithm is as follows:

Given X and Y positive integers < 2^30-1 
while true
  If X == Y
    Terminate fail
  If Y > X
    swap X,Y
  If (X,Y) found in Q
    Terminate success
  Add (X,Y) to Q
  X -= Y
  Y += Y

My brute force algorithm works, but on large numbers it takes a loooong time to complete. I'm assuming there is some sort of algorithm for this but my math is not good enough to know what that algorithm is. In other words, I don't know what question to ask.

Just looking for a pointer to the algorithm, if it exists.

Some examples 1,2 Terminates true in a loop as sub 1 gets 1 and the add gets 2 so you have 1,2 again

$1,3$ terminates false as $1,3 \rightarrow 2,2$

$1,7$ terminates false as $1,7 \rightarrow 2, 6 \rightarrow 4,4$

I'm looking for a shortcut instead of doing the full brute force chasing down the potential chain.

Answer 1

Let's instead play this game on the rational numbers $\frac{x}{x+y}$ and $\frac{y}{x+y}$. Key observation: the iteration consists of doubling the smallest of them, and then decreasing the largest one so that the sum is still $1$.

Under this observation, let's rewrite the game a bit: Given a rational number $q$ with $0<q<1$, an iteration consists of first checking whether $q>0.5$, and if it is, then replace it with $1-q$. Then, double it. You lose if you end up at $0.5$. Actually, I want to say that we lose if we end up at $1$, since that simplifies the next section. That is what would happen one iteration later anyways.

Now, what kind of rational numbers end up at $1$? Well, every time we double $q$, if the denominator was even, we can simplify by a factor of $2$, but if it was odd, then we can't. Also, the substitution to $1-q$ doesn't change neither the denominator nor whether the fraction can be simplified. So we keep dividing our denominator by $2$ until we eventually end up at an odd denominator. If said odd denominator is anything other than $1$ we will eventually win. Therefore the fractions $q$ that makes us lose are exactly the ones where the denominator, after simplifying, is a power of $2$.

Going back to our $x$ and $y$, this means that $x+y$ must be a power of $2$ if we are to ever lose. Well, not exactly, since if $(x,y)$ makes us lose, then so does $(kx,ky)$ for any positive integer $k$ (or, actually, any rational $k$ that makes $kx,ky$ positive integers). Therefore, the exact criterion is whether $\frac{x+y}{\gcd(x,y)}$ is a power of $2$.

Answer 2

Two numbers always form a loop eventually.

Notice that $x+y$ remains constant, and the number of pairs $(c,d)$ of non-negative integers that add to $x+y$ is $x+y+1$.

Therefore the program will always terminate after at most $2^{32}-1$ loops.