Después de las iteraciones$n$ del algoritmo de fracción continua, ¿qué tipo de números racionales habrán terminado?

Question

Para un número real positivo $r_0$, tenemos la continuación de la fracción algoritmo recursivo:

\begin{align} &r_n\in\mathbb{Z}\implies\text{terminate the algorithm}\\ &\text{else } r_{n+1} = \frac{1}{r_n-\operatorname{floor}(r_n)} \end{align}

Podemos decir que el algoritmo termina después de $n$ iteraciones si $r_n$ está definido y es un número entero.

De manera que el algoritmo termina después de $0$ iteraciones al $r_0$ es un número entero. Y se termina después de $1$ iteración al $r_0$ es un número entero más el recíproco de un número entero.

¿Qué se puede decir acerca de los números racionales para que el algoritmo termina después de $n$ iteraciones en general?

Estoy motivado por el siguiente. Me gustaría aplicar este algoritmo a un determinado número real de un número fijo de veces (por decir $10$ veces) para detectar si es racional. Asumiendo que esto es fácil para mí para comprobar si un número es un número entero, cómo los "grandes" (en términos de los numeradores y denominadores) son los números racionales que escapen a la detección, incluso después de $10$ iteraciones?

Answer 1

Con su comentario usted está en el camino correcto; véase aquí para una visión general acerca de las sucesivas approximants de fracciones continuas.

Cualquier número racional $r_0>0$ tiene un carácter de continuación de la fracción. Hay sucesivas approximants $${p_k\over q_k}\qquad(k\geq0)$$ to the initially given number $r_0$, which can be computed from the data $$a_k:=\lfloor r_k\rfloor\qquad(k\geq0)\ .$$ Cuando el algoritmo termina después de $n$ pasos a continuación $$r_0={p_n\over q_n}\ .$$ When it does not terminate after $n$ steps then $r_0$ is in fact irrational, or $r_0={\displaystyle{p_N\sobre q_N}}$ for some $N>n$.

Las fórmulas recursivas para $p_k$ $q_k$ muestran que estos números crecen más lento cuando todos los $a_k=1$ $\>(k>1)$; en caso de que el $p_k$ $q_k$ son esencialmente los números de Fibonacci. Así que cuando el algoritmo no termina después de $n$ pasos, a continuación, $r_0$ era en realidad irracional o de la forma ${p\over q}$ $p$ $q$ ambos, al menos, igual a la $(n+1)^{\rm st}$ número Fibonacci (verificación de la numeración oficial de estos).