{"id":4042,"date":"2014-03-25T22:09:34","date_gmt":"2014-03-25T20:09:34","guid":{"rendered":"http:\/\/pimedios.es\/?p=4042"},"modified":"2014-03-25T22:09:34","modified_gmt":"2014-03-25T20:09:34","slug":"el-algoritmo-voraz-de-sylvester","status":"publish","type":"post","link":"http:\/\/pimedios.jesussoto.es\/?p=4042","title":{"rendered":"El algoritmo voraz de Sylvester"},"content":{"rendered":"

\"\"<\/a>La matem\u00e1tica egipcia ten\u00eda predilecci\u00f3n por descomponer fracciones en suma de fracciones unitarias, preferentemente de dos o tres sumandos, aunque tambi\u00e9n las hay de cuatro. El por qu\u00e9 eleg\u00edan una suma a otra, por ejemplo $$\\frac{2}{9}=\\frac{1}{6}+\\frac{1}{18},$$ cuando se puede expresar como\u00a0$$\\frac{2}{9}=\\frac{1}{5}+\\frac{45}{18},$$ o la m\u00e1s simple\u00a0$$\\frac{2}{9}=\\frac{1}{9}+\\frac{1}{9},$$ sigue siendo controversia entre los historiadores. La hip\u00f3tesis m\u00e1s aceptada dice que entre varias descomposiciones eleg\u00edan aquella en la que la diferencia entre los denominadores era la m\u00e1s peque\u00f1a posible, \u00a1y no siempre! Cosas de no tener una metodolog\u00eda formal.<\/p>\n

\"\"<\/a>Con el tiempo, y el inter\u00e9s despertado, no solo en los arque\u00f3logos,\u00a0James Joseph Sylvester (1814-1897) se interes\u00f3 por representar cualquier racional como suma de fracciones unitarias, e ide\u00f3 un algoritmo.<\/p>\n

Partiendo de una fracci\u00f3n 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\u00f3n. Entonces:\u00a0\u00a0$$\\frac{p}{n}\u00a0=\\frac{p}{qp+r}=\\frac{1}{q+(r\/p)}.$$<\/p>\n

Como $r\/p<1$, resulta\u00a0$$\\frac{1}{q+1}<\\frac{p}{n}<\\frac{1}{q};$$ por tanto, la fracci\u00f3n unitaria mas cercana a $p\/n$ pero menor que ella es\u00a0$\\frac{1}{q+1}$. Calculemos la diferencia de ambas:\u00a0$$\\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,\u00a0$$\\frac{p}{n}=\\frac{1}{q+1}+\\frac{p-r}{n(q+1)}.$$<\/p>\n

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

Ve\u00e1moslo con un ejemplo:<\/p>\n

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

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

$$\\frac{3}{68}-\\frac{1}{23}=\\frac{1}{1564}.$$<\/p>\n

Por tanto,<\/p>\n

$$\\frac{5}{17}=\\frac{1}{4}+\\frac{1}{23}+\\frac{1}{1564}.$$<\/p>\n

Este algoritmo suele designarsele como algoritmo voraz de Sylvester; pero no es de \u00e9l. Sylvester lo redescubri\u00f3 en su publicaci\u00f3n de 1909, incorporando pruebas y formulaci\u00f3n que faltaba en la obra donde aparece: Liber Abaci<\/em>. S\u00ed fue Fibonacci quien lo trajo a occidente y lo enunci\u00f3 como mejora para encontrar la descomposici\u00f3n de fracciones.<\/p>\n

Sylvester en su articulo no menciona a Fibonacci, ello no es motivo suficiente para afirmar o negar si ya lo conoc\u00eda, incluso si pensaba que era obvio. S\u00ed 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\u00f3n de un racional $Q$ entre las fracciones $\\frac{1}{u_0-1}$ y\u00a0$\\frac{1}{u_0}$ m\u00e1s pr\u00f3ximas. As\u00ed $Q=\\frac{1}{u_0+\\delta}+Q’$. Repitiendo el proceso y analizando la relaci\u00f3n entre los diferentes $u_x$, encuentra la relaci\u00f3n $$u_{x+1}=u_x^2-u_x+1.$$<\/p>\n

Esta relaci\u00f3n de recurrencia es la que pasar\u00e1 a llamarse Sucesi\u00f3n de Sylvester<\/a>, y tiene una particularidad. Comencemos con $u_0=2$, entonces tendremos la sucesi\u00f3n<\/p>\n

2, 3, 7, 43, 1807, 3263443, 10650056950807,…<\/p>\n

Si consideramos la suma de sus rec\u00edprocos resulta que:<\/p>\n

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

Esta secuencia recursiva tiene otras peculiaridades y relaciones; pero esa es otra historia.<\/p>\n

Esta entrada participa en la Edici\u00f3n 5.2<\/a> Emmy Noether del Carnaval de Matem\u00e1ticas<\/a> cuyo anfitri\u00f3n es Matesdedavid<\/a>.<\/em><\/p>\n

Referencias:<\/h3>\n