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

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. • Your graph is really good. You might like this one as well. Jun 17 '20 at 1:01

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.

• Neat!$\phantom{}$ Jun 17 '20 at 0:29
• Many thanks also for the reference to the Euclidean alogrithm. Now seeing that all pairs have no common factor except for 1, it all makes more sense. I thought it could also be solved as a Calkin–Wilf tree, but your explanation makes much more sense. Jun 17 '20 at 10:59

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 } xy \\ +\infty & \text{if }x=y \end{cases}.$$