I wish to change my old algorithm by another old algorithm RATCONVERT

Question

I have an idea for my old problem was mentioned hereFRACTIONS. I saw one relationship between it and another one so I tried to optimize that given problem by similar method. For example,

$$\frac{1}{6}\rightarrow \frac{2}{7}\rightarrow \frac{3}{8}\rightarrow \frac{4}{9}\rightarrow \frac{5}{10}:=\frac{1}{2}\rightarrow \frac{2}{3}$$

I observe $$\frac{2}{3}= \frac{1}{1+ \frac{1}{2}}$$ $$\frac{1}{6}= \frac{1}{2\cdot 3}\rightarrow \frac{1}{2}$$ Because $\dfrac{1}{a}$ is always in the desired form, and what we need to do is finding $\dfrac{1}{a}\rightarrow \dfrac{1}{b}$ by the greatest divisor of $6$ is $3.$ This way is useful to create lowest terms with continued-fractions.

Another example: $$\frac{2}{3}\rightarrow \frac{3}{4}\rightarrow \cdots \rightarrow \frac{11}{14}\neq \frac{11}{15}$$ Because $$\frac{11}{15}= \frac{1}{1+ \frac{1}{2+ \frac{1}{1+ \frac{1}{3}}}}$$ and $$\frac{1}{6}< \frac{1}{3}< \frac{1}{2}$$ And for complex counter-example: $$\frac{2}{3}\rightarrow \frac{25}{26}\neq \frac{25}{34}= \frac{1}{1+ \frac{1}{2+ \frac{1}{1+ \frac{1}{3+ \frac{1}{2}}}}}$$ On the other hand, seems like it involving toRATCONVERT, I can't do it, at least, I completed the algorithm, I will show you in the environment C++:

#include <iostream>
#include <math.h>
using namespace std;
int main() {
    long long k, m, q;
    cin>>k>>m;
    long long r1=m, r2=k;
    int v1=0, v2=1;
    while (true) {
        if (v2>=sqrt(m/2)) {
            cout<<0<<", "<<0;
            break;
        }
        else {
            if (r2<sqrt(m/2)) {
                cout<<v2/sqrt(v2*v2)*r2<<", "<<sqrt(v2*v2);
                break;
            }
            else {
                q=round(r1/r2);
                r1=r1-q*r2;
                v1=v1-q*v2;
                swap(r1, r2);
                swap(v1, v2);
            }
        }
    }
}

So $u= \dfrac{Kv- r}{M}$ satisfied the conditions, how to change it to solve this problem, I need to the help, very much thank you.

Answer 1

Assuming that we are given four positive integers $a,b,c,d$ satisfying $$\gcd(a,b)=\gcd(c,d)=1,\qquad \frac ab\lt \frac cd\lt 1,\qquad \frac{bc-ad}{d-c}\in\mathbb Z$$I'll show a way to reduce the number of the steps from $\dfrac ab$ to $\dfrac cd$ when $D(a/b)\gt D(c/d)$ where $D(x/y):=y-x$.

In order to reduce the number of steps, we want to find the smallest positive integer $c$ such that there is an integer $k\ge 2$ satisfying $b+c\equiv a+c\equiv 0\pmod k$.

Since $b-a\equiv 0\pmod k$, we see that $k$ has to be a divisor of $b-a$.

For each such $k$, let $c_k:=k\left\lfloor\dfrac ak+1\right\rfloor-a$ where $c_k$ is the smallest positive integer such that $c\equiv -a\pmod k$, and $\lfloor x\rfloor $ denotes the greatest integer less than or equal to $x$.

Now, what we want is $\min(c_k)$ for which we have $$\dfrac ab\rightarrow \dfrac{a+\min(c_k)}{b+\min(c_k)}=\dfrac{\dfrac{a+\min(c_k)}{k'}}{\dfrac{b+\min(c_k)}{k'}}$$where $c_{k'}=\min(c_k)$.

Here, we can say that $\min(c_k)$ is smaller than the second smallest positive divisor $\min(k)$ of $b-a$ since $$c_k=k\left\lfloor\dfrac ak+1\right\rfloor-a\lt k\bigg(\dfrac ak+1\bigg)-a=k.$$

Also, since $c_k\ge k-a$, we can ignore $k$ such that $k-a\ge \min(k)$.

---

Example :

• If $(a,b,c,d)=(50,127,2,3)$, then since $D(a/b)\gt D(c/d)$ holds, we can reduce the number of the steps using the above method. The divisors larger than $1$ of $b-a=77$ are $k=7,11$ and $77$. Here, $k-a\ge\min(k)=7$ holds for $k=77$, so we can ignore $k=77$, and have $\min(c_7,c_{11},c_{77})=\min(c_7,c_{11})=\min(6,5)=5$ to get $\dfrac{50}{127}\to \dfrac{50+5}{127+5}=\dfrac{5}{12}$. Now, $D(5/12)\gt D(c/d)$ holds, so we can again reduce the number of the steps. Since $7$ is the only divisor larger than $1$ of $12-5=7$, we have $\dfrac{5}{12}\to \dfrac{5+c_7}{12+c_7}=\dfrac{5+2}{12+2}=\dfrac 12$ where we finally have $D(1/2)=D(2/3)$. In conclusion, we have$$\dfrac{50}{127}\to\bigg(\dfrac{50+5}{127+5}=\bigg)\dfrac {5}{12}\to\bigg(\dfrac{5+2}{12+2}=\bigg)\dfrac 12\to\frac 23$$where the number of the steps is $3$ which is smaller than $x=104$ satisfying $\dfrac{a+x}{b+x}=\dfrac cd$.