Why does this procedure terminate? Or are there any numbers for which it doesn't?

Question

I don't really have good formal education in theoretical mathematics, so please don't be upset if this is obvious question, but on the other hand I don't believe I am the first one to think of such problem. So let p,q be Natural numbers q != 0 (we will be thinking of them as a dividend and divisor of a fraction) and procedure looks more or less like that:

f(p,q): 
if (gcd(p,q) > 1) return f(p/gcd(p,q), q/gcd(p,q))
if (p/q > 1/3) then return f(p+1, q+4)
if (p/q < 1/3) then return f(p+1, q+1)
if (p/q == 1/3) then return WIN

so the case that it should end in some infinite number of steps is intuitive - when we are larger than 1/3 we step towards 1/4 and if we are smaller we step towards 1. Running simple script given result that for all pairs of numbers (up to 5 of decimal digits in size) it ends at some time, so my question is "Can anyone prove that this procedure finishes after some finite number of steps and not loops infinitely for any numbers p and q as described?"

Answer 1

Let's walk backwards from the final result: $3x-y=0$ (both $x$ and $y$ are integers).

Starting with any $x$ and $y$ the logic is as follows: when $3x - y <0$, we add one to both $x$ and $y$ so the expression becomes $3x+3-y-1=3x-y+2$. Increasing by $2$ we either hit $0$ or overshoot it by $1$.

When $3x-y>0$ we add one to $x$ and we add $4$ to $y$ so the expression becomes $3x+3-y-4=3x-y-1$. Now it's obvious that we cannot miss zero as we are decreasing the expression by one until we get to zero.

The logic that involves GCD just speeds up the process as it reduces $p$ and $q$, you do not really need it to get the win.

Answer 2

Let $(p_n, q_n)$ be the generated sequence, and consider $d_n = 3p_n - q_n$.

Case 1: If $d_n = 0$ for some $n$ then $\frac{p_n}{q_n} = \frac 13$, i.e. the recursion finishes after at most one more step.

Case 2: If $d_n < 0$ then $\frac{p_n}{q_n} < \frac 13$ and $$ d_{n+1} = 3(p_n + 1) - (q_n + 1) = d_n + 2 > d_n $$ if $\gcd(p_n, q_n) = 1$, otherwise $$ d_{n+1} = \frac{d_n}{\gcd(p_n, q_n)} > d_n \, . $$ So as long as $d_n < 0$, the sequence $(d_n)$ is a strictly increasing sequence of integers, which means that eventually $d_n = 0$ or $d_n > 0$.

Case 3: If $d_n > 0$ then $\frac{p_n}{q_n} > \frac 13$ and $$ d_{n+1} = 3(p_n + 1) - (q_n + 4) = d_n - 1 < d_n $$ if $\gcd(p_n, q_n) = 1$, otherwise $$ 0 < d_{n+1} = \frac{d_n}{\gcd(p_n, q_n)} < d_n \, . $$ So as long as $d_n > 0$, the sequence $(d_n)$ is strictly decreasing, and eventually reaches zero. (Note that $d_{n+1}$ cannot become negative again.)

So in all cases $d_n = 0$ eventually, which shows that the recursion always terminates. Concretely:

• If $\frac pq = \frac 13$ then the recursion finishes after at most one step (dividing by the $\gcd$). Example: $$ (2, 6) \to (1, 3) $$
• If $\frac pq < \frac 13$ then the recursion finishes after at most $$ \left\lceil \frac{q-3p}{2}\right\rceil + 2 $$ steps: $\left\lceil \frac{q-3p}{2}\right\rceil$ steps for reaching a state with $\frac pq \ge \frac 13$, possibly one more step for reaching a state with $\frac pq = \frac 13$, and possibly one more step for dividing by the $\gcd$. Example: $$ (1, 6) \to (2, 7) \to (3, 8) \to (4, 12) \to (1, 3) $$
• If $\frac pq > \frac 13$ then the recursion finishes after at most $$ 3p - q + 1 $$ steps: $3p-q$ steps for reaching a state with $\frac pq = \frac 13$, and possibly one more step for dividing by the $\gcd$. Example: $$ (3, 7) \to (4, 11) \to (5, 15) \to (1, 3) $$

The examples show that those bounds are best possible.