2
$\begingroup$

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.

Steps needed per (x,y)

$\endgroup$
  • $\begingroup$ Your graph is really good. You might like this one as well. $\endgroup$ – John L. Jun 17 at 1:01
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Neat!$\phantom{}$ $\endgroup$ – Steven Jun 17 at 0:29
  • $\begingroup$ 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. $\endgroup$ – CarlosSR Jun 17 at 10:59
0
$\begingroup$

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}. $$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.