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.