Saturday, 24 August 2013

After $n$ iterations of the continued fraction algorithm, what kind of rational numbers will have terminated?

After $n$ iterations of the continued fraction algorithm, what kind of
rational numbers will have terminated?

For a positive real number $r_0$, we have the continued fraction recursive
algorithm:
\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}
We would say the algorithm terminates after $n$ iterations if $r_n$ is
defined and it's an integer.
So the algorithm terminates after $0$ iterations when $r_0$ is an integer.
And it terminates after $1$ iteration when $r_0$ is an integer plus the
reciprocal of an integer.
What can be said about those rational numbers for which the algorithm
terminates after $n$ iterations in general?
I am motivated by the following. I would like to apply this algorithm to a
given real number a fixed number of times (say $10$ times) to detect if it
is rational. Assuming it is easy for me to test if a number is an integer,
how "big" (in terms of numerators and denominators) are the rational
numbers that will escape detection, even after $10$ iterations?

No comments:

Post a Comment