El algoritmo voraz de Sylvester

La matemática egipcia tenía predilección por descomponer fracciones en suma de fracciones unitarias, preferentemente de dos o tres sumandos, aunque también las hay de cuatro. El por qué elegían una suma a otra, por ejemplo $$\frac{2}{9}=\frac{1}{6}+\frac{1}{18},$$ cuando se puede expresar como $$\frac{2}{9}=\frac{1}{5}+\frac{45}{18},$$ o la más simple $$\frac{2}{9}=\frac{1}{9}+\frac{1}{9},$$ sigue siendo controversia entre los historiadores. La hipótesis más aceptada dice que entre varias descomposiciones elegían aquella en la que la diferencia entre los denominadores era la más pequeña posible, ¡y no siempre! Cosas de no tener una metodología formal.

Con el tiempo, y el interés despertado, no solo en los arqueólogos, James Joseph Sylvester (1814-1897) se interesó por representar cualquier racional como suma de fracciones unitarias, e ideó un algoritmo.

Partiendo de una fracción propia $\frac{p}{n}$ ($p<n$), sabemos que existen $q,r\in\mathbb{Z}$ tales que $n=qp+r$, con $r<p$; esto es el algoritmo de la división. Entonces:  $$\frac{p}{n} =\frac{p}{qp+r}=\frac{1}{q+(r/p)}.$$

Como $r/p<1$, resulta $$\frac{1}{q+1}<\frac{p}{n}<\frac{1}{q};$$ por tanto, la fracción unitaria mas cercana a $p/n$ pero menor que ella es $\frac{1}{q+1}$. Calculemos la diferencia de ambas: $$\frac{p}{n} -\frac{1}{q+1}=\frac{p(q+1)-n}{n(q+1)}=\frac{p(q+1)-(qp+r)}{n(q+1)}=\frac{p-r}{n(q+1)};$$ es decir, $$\frac{p}{n}=\frac{1}{q+1}+\frac{p-r}{n(q+1)}.$$

Ya tenemos nuestra fracción original expresada como la suma de una fracción unitaria más otra, cuyo numerador es menor que el numerador de partida. Si repetimos el proceso para la fracción $\frac{p-r}{n(q+1)}$ llegaremos a conseguir la suma buscada.

Veámoslo con un ejemplo:

$$\frac{5}{17}=\frac{5}{3\cdot 5+2}=\frac{1}{3+(2/5)}>\frac{1}{4}$$

$$\frac{5}{17}-\frac{1}{4}=\frac{3}{68}=\frac{3}{22\cdot 3+2}=\frac{1}{22+(2/3)}>\frac{1}{23};$$

$$\frac{3}{68}-\frac{1}{23}=\frac{1}{1564}.$$

Por tanto,

$$\frac{5}{17}=\frac{1}{4}+\frac{1}{23}+\frac{1}{1564}.$$

Este algoritmo suele designarsele como algoritmo voraz de Sylvester; pero no es de él. Sylvester lo redescubrió en su publicación de 1909, incorporando pruebas y formulación que faltaba en la obra donde aparece: Liber Abaci. Sí fue Fibonacci quien lo trajo a occidente y lo enunció como mejora para encontrar la descomposición de fracciones.

Sylvester en su articulo no menciona a Fibonacci, ello no es motivo suficiente para afirmar o negar si ya lo conocía, incluso si pensaba que era obvio. Sí conoce que los egipcios trabajaban con la fracciones de una forma similar. Puede ser que picado por la curiosidad Sylvester se dedicara a buscar la representación de un racional $Q$ entre las fracciones $\frac{1}{u_0-1}$ y $\frac{1}{u_0}$ más próximas. Así $Q=\frac{1}{u_0+\delta}+Q’$. Repitiendo el proceso y analizando la relación entre los diferentes $u_x$, encuentra la relación $$u_{x+1}=u_x^2-u_x+1.$$

Esta relación de recurrencia es la que pasará a llamarse Sucesión de Sylvester, y tiene una particularidad. Comencemos con $u_0=2$, entonces tendremos la sucesión

2, 3, 7, 43, 1807, 3263443, 10650056950807,…

Si consideramos la suma de sus recíprocos resulta que:

$$\sum_{i=0}^{\infty} \frac1{u_i} = \frac{1}{2} + \frac{1}{3} + \frac{1}{7} + \frac{1}{43} + \frac{1}{1807} + \cdots=1.$$

Esta secuencia recursiva tiene otras peculiaridades y relaciones; pero esa es otra historia.

Esta entrada participa en la Edición 5.2 Emmy Noether del Carnaval de Matemáticas cuyo anfitrión es Matesdedavid.

Referencias: