Fracciones continuas

Una fracción continua (continued fraction) es una representación de un número real como una secuencia convergente específica de números racionales. Son útiles en programación competitiva porque son fáciles de computar y se pueden usar de forma eficiente para encontrar la mejor aproximación racional posible del número real subyacente (entre todos los números cuyo denominador no exceda un valor dado).

Además de eso, las fracciones continuas están estrechamente relacionadas con el algoritmo de Euclides, lo que las hace útiles en un montón de problemas de teoría de números.

Representación en fracción continua

Se puede demostrar que cualquier número racional se puede representar como fracción continua de exactamente $2$ formas:

$$r = [a_0;a_1,\dots,a_k,1] = [a_0;a_1,\dots,a_k+1].$$

Además, la longitud $k$ de tal fracción continua se estima como $k = O(\log \min(p, q))$ para $r=\frac{p}{q}$.

El razonamiento detrás de esto quedará claro una vez que profundicemos en los detalles de la construcción de la fracción continua.

Nótese que para $r=[a_0;a_1,\dots]$ y un entero $k$, se cumple que $r+k = [a_0+k; a_1, \dots]$.

Otra observación importante es que $\frac{1}{r}=[0;a_0, a_1, \dots]$ cuando $a_0 > 0$ y $\frac{1}{r} = [a_1; a_2, \dots]$ cuando $a_0 = 0$.

De las definiciones de arriba, se puede concluir que $s_k \geq 1$ para $k \geq 1$.

Tratando $[a_0; a_1, \dots, a_k]$ como una expresión algebraica formal y permitiendo números reales arbitrarios en lugar de $a_i$, obtenemos

$$r = [a_0; a_1, \dots, a_{k-1}, s_k].$$

En particular, $r = [s_0] = s_0$. Por otro lado, podemos expresar $s_k$ como

$$s_k = [a_k; s_{k+1}] = a_k + \frac{1}{s_{k+1}},$$

lo que significa que podemos computar $a_k = \lfloor s_k \rfloor$ y $s_{k+1} = (s_k - a_k)^{-1}$ a partir de $s_k$.

La secuencia $a_0, a_1, \dots$ está bien definida salvo que $s_k=a_k$, lo cual solo ocurre cuando $r$ es un número racional.

Así, la representación en fracción continua está definida de forma única para cualquier número irracional $r$.

Implementación

En los fragmentos de código asumiremos principalmente fracciones continuas finitas.

A partir de $s_k$, la transición a $s_{k+1}$ se ve como

$$s_k =\left\lfloor s_k \right\rfloor + \frac{1}{s_{k+1}}.$$

De esta expresión, el siguiente cociente completo $s_{k+1}$ se obtiene como

$$s_{k+1} = \left(s_k-\left\lfloor s_k\right\rfloor\right)^{-1}.$$

Para $s_k=\frac{p}{q}$ significa que

$$s_{k+1} = \left(\frac{p}{q}-\left\lfloor \frac{p}{q} \right\rfloor\right)^{-1} = \frac{q}{p-q\cdot \lfloor \frac{p}{q} \rfloor} = \frac{q}{p \bmod q}.$$

Así, el cómputo de una representación en fracción continua para $r=\frac{p}{q}$ sigue los pasos del algoritmo de Euclides para $p$ y $q$.

De esto también se sigue que $\gcd(p_k, q_k) = 1$ para $\frac{p_k}{q_k} = [a_0; a_1, \dots, a_k]$. Por tanto, los convergentes son siempre irreducibles.

=== “C++” cpp auto fraction(int p, int q) { vector<int> a; while(q) { a.push_back(p / q); tie(p, q) = make_pair(q, p % q); } return a; } === “Python” py def fraction(p, q): a = [] while q: a.append(p // q) p, q = q, p % q return a

Resultados clave

Para dar alguna motivación para el estudio posterior de las fracciones continuas, damos ahora algunos hechos clave.

El último hecho permite encontrar las mejores aproximaciones racionales de $r$ comprobando sus semiconvergentes.

Abajo se encontrará la explicación adicional y un poco de intuición e interpretación de estos hechos.

Convergentes

Miremos más de cerca los convergentes que se definieron antes. Para $r=[a_0, a_1, a_2, \dots]$, sus convergentes son

$$\begin{gather} r_0=[a_0],\r_1=[a_0, a_1],\ \dots,\ r_k=[a_0, a_1, \dots, a_k]. \end{gather}$$

Los convergentes son el concepto central de las fracciones continuas, así que es importante estudiar sus propiedades.

Para el número $r$, su $k$-ésimo convergente $r_k = \frac{p_k}{q_k}$ se puede computar como

$$r_k = \frac{P_k(a_0,a_1,\dots,a_k)}{P_{k-1}(a_1,\dots,a_k)} = \frac{a_k p_{k-1} + p_{k-2}}{a_k q_{k-1} + q_{k-2}},$$

donde $P_k(a_0,\dots,a_k)$ es el continuante , un polinomio multivariado definido como

$$P_k(x_0,x_1,\dots,x_k) = \det$$$$\begin{bmatrix} x_k & 1 & 0 & \dots & 0 \ -1 & x_{k-1} & 1 & \dots & 0 \ 0 & -1 & x_2 & . & \vdots \ \vdots & \vdots & . & \ddots & 1 \ 0 & 0 & \dots & -1 & x_0 \end{bmatrix}$$_{\textstyle .}

Así, $r_k$ es una medianta  ponderada de $r_{k-1}$ y $r_{k-2}$.

Por consistencia, se definen dos convergentes adicionales $r_{-1} = \frac{1}{0}$ y $r_{-2} = \frac{0}{1}$.

Implementación

Computaremos los convergentes como un par de secuencias $p_{-2}, p_{-1}, p_0, p_1, \dots, p_k$ y $q_{-2}, q_{-1}, q_0, q_1, \dots, q_k$:

=== “C++” cpp auto convergents(vector<int> a) { vector<int> p = {0, 1}; vector<int> q = {1, 0}; for(auto it: a) { p.push_back(p[p.size() - 1] * it + p[p.size() - 2]); q.push_back(q[q.size() - 1] * it + q[q.size() - 2]); } return make_pair(p, q); } === “Python” py def convergents(a): p = [0, 1] q = [1, 0] for it in a: p.append(p[-1]*it + p[-2]) q.append(q[-1]*it + q[-2]) return p, q

Árboles de fracciones continuas

Hay dos formas principales de unir todas las fracciones continuas posibles en estructuras de árbol útiles.

Árbol de Stern-Brocot

El árbol de Stern-Brocot es un árbol binario de búsqueda que contiene todos los números racionales positivos distintos.

El árbol se ve en general así:

Las fracciones $\frac{0}{1}$ y $\frac{1}{0}$ se mantienen “virtualmente” en los lados izquierdo y derecho del árbol respectivamente.

Luego la fracción en un nodo es una medianta $\frac{a+c}{b+d}$ de dos fracciones $\frac{a}{b}$ y $\frac{c}{d}$ por encima de él.

La recurrencia $\frac{p_k}{q_k}=\frac{a_k p_{k-1} + p_{k-2}}{a_k q_{k-1} + q_{k-2}}$ significa que la representación en fracción continua codifica el camino a $\frac{p_k}{q_k}$ en el árbol. Para encontrar $[a_0; a_1, \dots, a_{k}, 1]$, hay que hacer $a_0$ movimientos a la derecha, $a_1$ movimientos a la izquierda, $a_2$ movimientos a la derecha y así sucesivamente hasta $a_k$.

El padre de $[a_0; a_1, \dots, a_k,1]$ entonces es la fracción obtenida al dar un paso atrás en la última dirección usada.

En otras palabras, es $[a_0; a_1, \dots, a_k-1,1]$ cuando $a_k > 1$ y $[a_0; a_1, \dots, a_{k-1}, 1]$ cuando $a_k = 1$.

Así los hijos de $[a_0; a_1, \dots, a_k, 1]$ son $[a_0; a_1, \dots, a_k+1, 1]$ y $[a_0; a_1, \dots, a_k, 1, 1]$.

Indexemos el árbol de Stern-Brocot. Al vértice raíz se le asigna índice $1$. Luego para un vértice $v$, el índice de su hijo izquierdo se asigna cambiando el bit líder de $v$ de $1$ a $10$ y para el hijo derecho, se asigna cambiando el bit líder de $1$ a $11$:

En esta indexación, la representación en fracción continua de un número racional especifica la codificación por longitud de racha  (run-length encoding) de su índice binario.

Para $\frac{5}{2} = [2;2] = [2;1,1]$, su índice es $1011_2$ y su codificación por longitud de racha, considerando bits en orden ascendente, es $[2;1,1]$.

Otro ejemplo es $\frac{2}{5} = [0;2,2]=[0;2,1,1]$, que tiene índice $1100_2$ y su codificación por longitud de racha es, en efecto, $[0;2,2]$.

Vale la pena notar que el árbol de Stern-Brocot es, de hecho, un treap. Es decir, es un árbol binario de búsqueda por $\frac{p}{q}$, pero es un heap tanto por $p$ como por $q$.

# [a0; a1, ..., ak] -> [a0, a1, ..., ak-1, 1]
def expand(a):
    if a: # empty a = inf
        a[-1] -= 1
        a.append(1)
    return a

# return a-eps, a+eps
def pm_eps(a):
    b = expand(a.copy())
    a.append(float('inf'))
    b.append(float('inf'))
    return (a, b) if less(a, b) else (b, a)
```

    p, q = middle(p0, q0, p1, q1)
    return str(q) + ' ' + str(p)
```

Árbol de Calkin-Wilf

Una forma algo más simple de organizar fracciones continuas en un árbol binario es el árbol de Calkin-Wilf .

El árbol se ve en general así:

En la raíz del árbol se ubica el número $\frac{1}{1}$. Luego, para el vértice con un número $\frac{p}{q}$, sus hijos son $\frac{p}{p+q}$ y $\frac{p+q}{q}$.

A diferencia del árbol de Stern-Brocot, el árbol de Calkin-Wilf no es un árbol binario de búsqueda, así que no se puede usar para realizar búsqueda binaria racional.

En el árbol de Calkin-Wilf, el padre directo de una fracción $\frac{p}{q}$ es $\frac{p-q}{q}$ cuando $p>q$ y $\frac{p}{q-p}$ en caso contrario.

Para el árbol de Stern-Brocot, usamos la recurrencia de convergentes. Para trazar la conexión entre la fracción continua y el árbol de Calkin-Wilf, deberíamos recordar la recurrencia de los cocientes completos. Si $s_k = \frac{p}{q}$, entonces $s_{k+1} = \frac{q}{p \mod q} = \frac{q}{p-\lfloor p/q \rfloor \cdot q}$.

Por otro lado, si vamos repetidamente de $s_k = \frac{p}{q}$ a su padre en el árbol de Calkin-Wilf cuando $p > q$, terminaremos en $\frac{p \mod q}{q} = \frac{1}{s_{k+1}}$. Si continuamos haciéndolo, terminaremos en $s_{k+2}$, luego $\frac{1}{s_{k+3}}$ y así sucesivamente. De esto podemos deducir que:

1. Cuando $a_0> 0$, el padre directo de $[a_0; a_1, \dots, a_k]$ en el árbol de Calkin-Wilf es $\frac{p-q}{q}=[a_0 - 1; a_1, \dots, a_k]$.
2. Cuando $a_0 = 0$ y $a_1 > 1$, su padre directo es $\frac{p}{q-p} = [0; a_1 - 1, a_2, \dots, a_k]$.
3. Y cuando $a_0 = 0$ y $a_1 = 1$, su padre directo es $\frac{p}{q-p} = [a_2; a_3, \dots, a_k]$.

Correspondientemente, los hijos de $\frac{p}{q} = [a_0; a_1, \dots, a_k]$ son

1. $\frac{p+q}{q}=1+\frac{p}{q}$, que es $[a_0+1; a_1, \dots, a_k]$,
2. $\frac{p}{p+q} = \frac{1}{1+\frac{q}{p}}$, que es $[0, 1, a_0, a_1, \dots, a_k]$ para $a_0 > 0$ y $[0, a_1+1, a_2, \dots, a_k]$ para $a_0=0$.

Notablemente, si enumeramos los vértices del árbol de Calkin-Wilf en el orden de búsqueda en anchura (es decir, la raíz tiene número $1$, y los hijos del vértice $v$ tienen índices $2v$ y $2v+1$ respectivamente), el índice del número racional en el árbol de Calkin-Wilf sería el mismo que en el árbol de Stern-Brocot.

Así, los números en los mismos niveles del árbol de Stern-Brocot y del árbol de Calkin-Wilf son los mismos, pero su ordenamiento difiere a través de la permutación de inversión de bits .

Convergencia

Para el número $r$ y su $k$-ésimo convergente $r_k=\frac{p_k}{q_k}$ se cumple la siguiente fórmula:

$$r_k = a_0 + \sum\limits_{i=1}^k \frac{(-1)^{i-1}}{q_i q_{i-1}}.$$

En particular, significa que

$$r_k - r_{k-1} = \frac{(-1)^{k-1}}{q_k q_{k-1}}$$

y

$$p_k q_{k-1} - p_{k-1} q_k = (-1)^{k-1}.$$

De esto podemos concluir que

$$\left| r-\frac{p_k}{q_k} \right| \leq \frac{1}{q_{k+1}q_k} \leq \frac{1}{q_k^2}.$$

La última desigualdad se debe al hecho de que $r_k$ y $r_{k+1}$ generalmente se ubican en lados distintos de $r$, así

$$|r-r_k| = |r_k-r_{k+1}|-|r-r_{k+1}| \leq |r_k - r_{k+1}|.$$

Explicación detallada

Para estimar $|r-r_k|$, empezamos estimando la diferencia entre convergentes adyacentes. Por definición,

$$\frac{p_k}{q_k} - \frac{p_{k-1}}{q_{k-1}} = \frac{p_k q_{k-1} - p_{k-1} q_k}{q_k q_{k-1}}.$$

Reemplazando $p_k$ y $q_k$ en el numerador con sus recurrencias, obtenemos

$$\begin{array}{rllll}& {\displaystyle p_k{q}_{k-1}-p_{k-1}{q}_k}& {\displaystyle =(a_k{p}_{k-1}+p_{k-2})q_{k-1}-p_{k-1}(a_k{q}_{k-1}+q_{k-2})}& & \\ & {\displaystyle }& {\displaystyle =p_{k-2}{q}_{k-1}-p_{k-1}{q}_{k-2},}& & \end{array}$$$$\begin{align} p_k q_{k-1} - p_{k-1} q_k &= (a_k p_{k-1} + p_{k-2}) q_{k-1} - p_{k-1} (a_k q_{k-1} + q_{k-2}) \&= p_{k-2} q_{k-1} - p_{k-1} q_{k-2},\end{align}$$

así el numerador de $r_k - r_{k-1}$ es siempre el numerador negado de $r_{k-1} - r_{k-2}$. Este, a su vez, es igual a $1$ para

$$r_1 - r_0=\left(a_0+\frac{1}{a_1}\right)-a_0=\frac{1}{a_1},$$

así

$$r_k - r_{k-1} = \frac{(-1)^{k-1}}{q_k q_{k-1}}.$$

Esto da una representación alternativa de $r_k$ como suma parcial de una serie infinita:

$$r_k = (r_k - r_{k-1}) + \dots + (r_1 - r_0) + r_0 = a_0 + \sum\limits_{i=1}^k \frac{(-1)^{i-1}}{q_i q_{i-1}}.$$

De la relación recurrente se sigue que $q_k$ aumenta de forma monótona al menos tan rápido como los números de Fibonacci, así

$$r = \lim\limits_{k \to \infty} r_k = a_0 + \sum\limits_{i=1}^\infty \frac{(-1)^{i-1}}{q_i q_{i-1}}$$

siempre está bien definido, ya que la serie subyacente siempre converge. Notablemente, la serie residual

$$r-r_k = \sum\limits_{i=k+1}^\infty \frac{(-1)^{i-1}}{q_i q_{i-1}}$$

tiene el mismo signo que $(-1)^k$ debido a lo rápido que disminuye $q_i q_{i-1}$. Por tanto los $r_k$ de índice par se aproximan a $r$ desde abajo mientras que los $r_k$ de índice impar se aproximan desde arriba:

De esta imagen podemos ver que

$$|r-r_k| = |r_k - r_{k+1}| - |r-r_{k+1}| \leq |r_k - r_{k+1}|,$$

así la distancia entre $r$ y $r_k$ nunca es mayor que la distancia entre $r_k$ y $r_{k+1}$:

$$\left|r-\frac{p_k}{q_k}\right| \leq \frac{1}{q_k q_{k+1}} \leq \frac{1}{q_k^2}.$$