This problem is a part of another (programming) problem on which I am working, the start of which requires us to identify a certain pattern, I believe.
We are given a pair of positive integers x and y. We are going to perform an operation on this pair repeatedly to obtain a pair with equal values. We could as well say that this operation tries to balance this pair of integers so as to make them equal. The balancing operation is as follows: If the pair has unequal values, take the minimum, add it to the smaller integer and subtract it from the larger one. If the pair still has unequal values, repeat this operation on the new values. The task is to find whether this operation will run forever or eventually stop(making the values equal)? Can this be determined by seeing the initial input itself?
Hint for remembering the operation easily: The smaller one gets doubled, the larger one diminishes by value equal to the smaller one. See examples below.
Example: Start with (1, 4). We see that (1, 4) --> (2, 3) --> (4, 1) --> (3, 2) --> (1, 4). At this point it is clear that this operation will not give equal values for the pair(1, 4). Also, at the point when we got the interchanged values (4, 1), we could say that they are going to be repeated (I guess).
Example: Start with (1, 1). We see that the numbers are already equal. So, this operation is not applied. Or, we could say the algorithm/operation terminated at the start itself.
Example: Start with (5, 8). We see that (5, 8) --> (10, 3) --> (7, 6) --> (1, 12) --> (2, 11) --> (4, 9) --> (8, 5) --> (3, 10). If ordering is ignored, the values look the same as before. They are in cycle. It will not give equal values ever.
Example: Start with (1, 3). We see that (1, 3) --> (2, 2). Operation terminated since the pair has equal values now.
Since $x+y$ remains constant, this is essentially a 1D problem. 2D is just smoke and mirrors.
Let us denote $x+y=2n$ (because if the sum is odd, good luck trying to split it in equal halves). Let us suppose that on the first step one of the integers in the pair is $x$, because er, well, that's what it is. What will it be on the next step? There are two options:
By the same logic, on the next step we'll get $4x\pmod{2n}$, and so on.
So that's what is going on: we iterate through various remainders $2^k\cdot x\pmod{2n}$. We'll inevitably start going in cycles at some point or another, because there are only so many different remainders. Now the question is: will it be a cycle of size 1 (or rather, the cycle of size 1, because there is only one), or not? In other words, will our sequence ever hit $n\pmod{2n}$, or not?
Let's say $2^m$ is the greatest power of 2 that divides $n$. In other words, $n=2^m\cdot l$, where $l$ is odd. Now here is the deal: $\pmb x$ must be divisible by $\pmb l$. If it is, we'll hit $n$; if it isn't, we won't.
How so?
First the negative part. Any number which equals $n\pmod{2n}$ should be divisible by $l$, but if $x$ isn't, then neither is any of the $2^k\cdot x$, so we're out of luck.
Now the positive part. Let's say $x$ is some odd number times $2^p$. Obviously, $k<m$ (otherwise $x$ would be divisible by $l$ and by $2^m$, which means it would be divisible by $n$, which means it would be $n$ and the journey would end right where it started). Well, on the next step it would be $p+1$ instead of $p$, and so on, until we reach $m$. At that point, our $2^k\cdot x$ is divisible by $l$ and by $2^m$, which means it is divisible by $n$, but not by $2n$, which means... see above.
As a particular case, if $n$ is a power of 2, then any $x$ will do.
So it goes.