¿Cuándo $(a,b) \to (2a, b-a)$ terminar? ($a \leq b$)

Question

Tengo el siguiente problema.

Vamos a tener dos números enteros $a$$b$, suponga $a \leq b$ (si no, cambiamos de ellos)

El algoritmo es solo un paso, producir nuevos números: $2a$ $b-a$

El algoritmo se detiene cuando $a = b$, de lo contrario va a ciclo infinitamente.

Hasta el momento, tengo que para cualquier enteros $a$ $b$ algoritmo va a parar $\leftrightarrow$ $\frac{b}{a} = 2^n - 1$ o $\frac{b}{a}=(2^n + 1)/(2^n - 1)$ o $\frac{b}{a}=(2 ^ {n+1} + 2 ^ n - 1)/(2 ^ n + 1)$

Pero no puedo llegar a algo más simple. Realmente me encantaría ver algunos consejos o soluciones a este! Gracias de antemano

Answer 1

Problema interesante.

Supuse $a \gt 0$.

Creo que las siguientes obras:

Deje $$\frac{a}{b} = \frac{p}{q}$$

donde $\text{gcd}(p,q) = 1$ $p, q \gt 0$

Entonces el algoritmo termina el fib $$p+q = 2^m$$ where $m$ is an integer $\ge 1$

Prueba:

Es suficiente como para considerar la $\text{gcd}(a,b) = 1$ ($p = a, q = b$).

También observe que cada paso del algoritmo mantiene a $a+b$ de la misma. Así que supongamos $a,b$ son ambos impares (si su suma fue extraño, entonces nunca podremos obtener dos números iguales).

También tenga en cuenta que el algoritmo termina por $(a,b)$ fib se termina por $(ca, cb)$ donde $c \neq 0$

Ahora podemos hacer un mapa de $(a,b)$ $\left(a, \frac{b-a}{2}\right)$dividiendo un $2$.

Observe que $\text{gcd}\left(a, \frac{b-a}{2}\right) = 1$

Por lo tanto, podemos seguir dividiendo a cabo una $2$ después de cada paso y, finalmente, terminar con $(1,1)$ (debido a $\text{gcd}$ permanece $1$) o golpear a un punto en el que la suma se convierte en un número impar (ya no se puede dividir un $2$), y tenemos que entrar en un ciclo. El primero corresponde a $a+b = 2^m$, y la última corresponde a $a+b = 2^{n}(2k+1)$.