Algorithm to get the number of iterations needed, if possible, to get an specific 2 element array

Question

I am fairly new to algorithms and I am dealing with a problem I cannot fully translate into mathematical language.

So, I am given the array [1,1] and I can only perform one sum between their numbers per step, ie you can only pick between:

[x(s+1), y(s+1)]=[x(s)+y(s),y(s)]

or

[x(s+1),y(s+1)]=[x(s), x(s)+y(s)]

but not both at the same time

Thus,

0: [1,1]
1: [2,1],                      [1,2]
2: [3,1],        [2,3],        [3,2],        [1,3]
3: [4,1], [3,4], [5,3], [2,5], [5,2], [3,5], [4,3], [1,4]
...and so on.

The goal is to know how many steps are needed in order to get a given [x,y] array.

This far, I know that

if (min(x,y)==1) --> steps =max(x,y)-1

if (x%2 ==0 and y%2==0) (both even) --> steps= not possible
if (max(x,y)%min(x,y) == 0) (one is multiple of the other or x,y are the same ) --> steps= not possible
if (x%3 ==0 and y%3==0) (both divisble by 3) --> steps= not possible

Also I plotted for each pair (x,y) how many steps are needed, and I can see a pattern happening for every multiple of x or y, but I can't write it as a mathematical function when x or y is >= 5.

Any guidance will be much appreciated.

Answer 1

You have observed several impossible situations for $x$ and $y$, such as when $x$ and $y$ are both even or multiples of $3$, etc. More generally, we have the following characterization. For all positive integer $x$ and $y$,

$$(x,y)\text{ is reachable} \iff \gcd(x,y)=1$$ where $\gcd(x,y)$ is the greatest common divisor of $x$ and $y$. That characterization can be proved easily by mathematical induction on $n=x+y$, since $$\gcd(x,y)=\gcd(x, x+y)=\gcd(x+y,y).$$

"The goal is to know how many steps are needed in order to get a given pair $(x,y)$." Here is a simple Python program that should be fast enough. It takes less than a hundredth of a second even if $x$ and $y$ have hundreds of decimal digits. The crux of the program is, count += x // y and x, y = y, x % y, which uses integer division and remainder to reduce $x$ to be smaller than $y$.

def number_of_iterations_needed(x, y):
    count = 0

    if x < y:
        x, y = y, x
    # Now x >= y

    while x % y != 0:
        count += x // y
        x, y = y, x % y
    # Now x % y == 0

    if y != 1:
        return None  # impossible
    else:
        count += x - y
        return count

In fact, the above program is just an augmented version of the well-known Euclidean algorithm, the granddaddy of all algorithms. Its time-complexity should be about the same as the time-complexity of the Euclidean algorithm, which is $O(\ln(\min(x,y))$. It uses about $O(1)$ space.

If you are searching for a closed form for the number of iterations needed given $x$ and $y$, you will probably not be able to find one since, as indicated on that Wikipedia page, nobody has come up with a closed form after more than two thousand years.

Answer 2

You can solve this problem in time $O(xy)$ using dynamic programming.

For $x,y \ge 1$, let $OP[x,y]$ be the minimum number of operations needed to obtain array $[x,y]$. If it is impossible to obtain array $[x,y]$ let $OP[x,y] = + \infty$.

Then $OP[1,1]=0$ and, for $x>1$ or $y>1$: $$ OP[x,y] = \begin{cases} 1 + OPT[x, y-x] & \text{if } x<y \\ 1 + OPT[x-y, y] & \text{if } x>y \\ +\infty & \text{if }x=y \end{cases}. $$