Algoritmo voraz para fracciones egipcias

En matemáticas , el algoritmo voraz para fracciones egipcias es un algoritmo voraz , descrito por primera vez por Fibonacci , para transformar números racionales en fracciones egipcias . Una fracción egipcia es una representación de una fracción irreducible como suma de fracciones unitarias distintas , como ⁠ 5 / 6 ⁠ = ⁠ 1 / 2 ⁠ + ⁠ 1 / 3 ⁠ . Como su nombre indica, estas representaciones se han utilizado desde el antiguo Egipto , pero el primer método sistemático publicado para construir tales expansiones se describió en 1202 en el Liber Abaci de Leonardo de Pisa (Fibonacci). ^{[ 1 ]} Se llama algoritmo voraz porque en cada paso el algoritmo elige de forma voraz la mayor fracción unitaria posible que se puede utilizar en cualquier representación de la fracción restante.

Fibonacci en realidad enumera varios métodos diferentes para construir representaciones de fracciones egipcias. ^{[ 2 ]} Incluye el método voraz como último recurso para situaciones en las que fallan varios métodos más simples; véase Fracción egipcia para una lista más detallada de estos métodos. El método voraz, y sus extensiones para la aproximación de números irracionales, han sido redescubiertos varias veces por matemáticos modernos, ^{[ 3 ]} el primero y más notable por JJ Sylvester ( 1880 ) ^{[ 4 ]} Un método de expansión estrechamente relacionado que produce aproximaciones más cercanas en cada paso al permitir que algunas fracciones unitarias en la suma sean negativas data de Lambert (1770) . 

La expansión producida por este método para un número${\displaystyle x}$se denomina expansión egipcia codiciosa , expansión de Sylvester o expansión de Fibonacci-Sylvester de${\displaystyle x}$Sin embargo, el término expansión de Fibonacci generalmente se refiere, no a este método, sino a la representación de números enteros como sumas de números de Fibonacci .

El algoritmo de Fibonacci expande la fracción${\displaystyle x/y<1}$ser representado, realizando repetidamente el reemplazo $${\displaystyle {\frac {x}{y}}={\frac {1}{\left\lceil {\frac {y}{x}}\right\rceil }}+{\frac {(-y){\bmod {x}}}{y\left\lceil {\frac {y}{x}}\right\rceil }}}$$ (simplificando el segundo término en esta sustitución según sea necesario). Por ejemplo: $${\displaystyle {\frac {7}{15}}={\frac {1}{3}}+{\frac {2}{15}}={\frac {1}{3}}+{\frac {1}{8}}+{\frac {1}{120}}.}$$ En esta expansión, el denominador 3 de la primera fracción unitaria es el resultado de redondear ⁠ 15 / 7 ⁠ al entero superior más cercano, y la fracción restante ⁠ 2 / 15 ⁠ es el resultado de simplificar ⁠ −15 mod 7 / 15 × 3 ⁠ = ⁠ 6 / 45 ⁠ . El denominador de la segunda fracción unitaria, 8, es el resultado de redondear ⁠ 15 / 2 ⁠ al entero superior más cercano, y la fracción restante ⁠ 1 / 120 ⁠ es lo que queda de ⁠ 7 / 15 ⁠ después de restar tanto ⁠ 1 / 3 ⁠ como ⁠ 1 / 8 ⁠ .  

Como cada paso de expansión reduce el numerador de la fracción restante a expandir, este método siempre termina con una expansión finita; sin embargo, en comparación con las expansiones del antiguo Egipto o con métodos más modernos, este método puede producir expansiones bastante largas, con denominadores grandes. Por ejemplo, este método expande $${\displaystyle {\frac {5}{121}}={\frac {1}{25}}+{\frac {1}{757}}+{\frac {1}{763\,309}}+{\frac {1}{873\,960\,180\,913}}+{\frac {1}{1\,527\,612\,795\,642\,093\,418\,846\,225}},}$$ mientras que otros métodos conducen a una expansión mucho mejor $${\displaystyle {\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}.}$$Wagon (1991) sugiere un ejemplo aún más problemático, ⁠ 31 / 311 ⁠ . El método voraz conduce a una expansión con diez términos, el último de los cuales tiene más de 500 dígitos en su denominador; sin embargo, ⁠ 31 / 311 ⁠ tiene una representación no voraz mucho más corta, ⁠ 1 / 12 ⁠ + ⁠ 1 / 63 ⁠ + ⁠ 1 / 2799 ⁠ + ⁠ 1 / 8708 ⁠ .

La secuencia de Sylvester 2, 3, 7, 43, 1807, ... ( OEIS : A000058  ) puede verse como generada por una expansión voraz infinita de este tipo para el número 1, donde en cada paso elegimos el denominador ⌊ ⁠ y / x ⁠ ⌋ + 1 en lugar de ⌈ ⁠ y / x ⁠ ⌉ . Truncando esta secuencia a k términos y formando la fracción egipcia correspondiente, por ejemplo (para k  =  4) $${\displaystyle {\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}={\frac {1805}{1806}}}$$ da como resultado la subestimación más cercana posible de 1 por cualquier fracción egipcia de k términos. ^{[ 5 ]} Es decir, por ejemplo, cualquier fracción egipcia para un número en el intervalo abierto ( ⁠ 1805 / 1806 ⁠ , 1) requiere al menos cinco términos. Curtiss (1922) describe una aplicación de estos resultados de aproximación más cercana en la cota inferior del número de divisores de un número perfecto , mientras que Stong (1983) describe aplicaciones en la teoría de grupos . 

Cualquier fracción ⁠ x / y ⁠ requiere como máximo x términos en su expansión voraz. Mays (1987) y Freitag & Phillips (1999) examinan las condiciones bajo las cuales el método voraz produce una expansión de ⁠ x / y ⁠ con exactamente x términos; estas pueden describirse en términos de condiciones de congruencia en y .

• Cada fracción 1 / y requiere un término en su expansión voraz; la fracción más simple de este tipo es 1 / 1 .
• Toda fracción ⁠ 2 / y ⁠ requiere dos términos en su expansión voraz si y solo si y ≡ 1 (mod 2) ; la fracción más simple de este tipo es ⁠ 2 / 3 ⁠ .
• Una fracción ⁠ 3 / y ⁠ requiere tres términos en su expansión voraz si y solo si y ≡ 1 (mod 6) , porque entonces − y mod x = 2 y ⁠ y ( y + 2) / 3 ⁠ es impar, por lo que la fracción restante después de un solo paso de la expansión voraz,$${\displaystyle {\frac {(-y){\bmod {x}}}{y\left\lceil {\frac {y}{x}}\right\rceil }}={\frac {2}{\,{\frac {y(y+2)}{3}}\,}}}$$en términos más simples. La fracción más simple ⁠ 3 / y ⁠ con una expansión de tres términos es ⁠ 3 / 7 ⁠ .
• Una fracción ⁠ 4 / y ⁠ requiere cuatro términos en su expansión voraz si y solo si y ≡ 1 o 17 (mod 24) , ya que entonces el numerador − y mod x de la fracción restante es 3 y el denominador es 1 (mod 6) . La fracción más simple ⁠ 4 / y ⁠ con una expansión de cuatro términos es ⁠ 4 / 17 ⁠ . La conjetura de Erdős-Straus afirma que todas las fracciones ⁠ 4 / y ⁠ tienen una expansión con tres o menos términos, pero cuando y ≡ 1 o 17 (mod 24) tales expansiones deben encontrarse por métodos distintos al algoritmo voraz, estando el caso 17 (mod 24) cubierto por la relación de congruencia 2 (mod 3) .

De forma más general, la secuencia de fracciones ⁠ x / y ⁠ que tienen expansiones voraces de x términos y que tienen el denominador y más pequeño posible para cada x es

${\displaystyle 1,{\frac {2}{3}},{\frac {3}{7}},{\frac {4}{17}},{\frac {5}{31}},{\frac {6}{109}},{\frac {7}{253}},{\frac {8}{97}},{\frac {9}{271}},\dots }$(secuencia A048860 en el OEIS ).

Stratemeyer (1930) y Salzer (1947) describen un método para encontrar una aproximación precisa de las raíces de un polinomio basado en el método voraz. Su algoritmo calcula la expansión voraz de una raíz; en cada paso de esta expansión, mantiene un polinomio auxiliar cuya raíz es la fracción restante a expandir. Consideremos como ejemplo la aplicación de este método para encontrar la expansión voraz de la razón áurea , una de las dos soluciones de la ecuación polinómica P ₀ ( x ) = x ² − x − 1 = 0. El algoritmo de Stratemeyer y Salzer realiza la siguiente secuencia de pasos:

1. Dado que P ₀ ( x ) < 0 para x  =  1, y P ₀ ( x ) > 0 para todo x ≥ 2 , debe haber una raíz de P ₀ ( x ) entre 1 y 2. Es decir, el primer término de la expansión voraz de la razón áurea es ⁠ 1 / 1 ⁠ . Si x ₁ es la fracción restante después del primer paso de la expansión voraz, satisface la ecuación P ₀ ( x ₁ + 1) = 0 , que se puede expandir como P ₁ ( x ₁ ) = x ² ₁ + x ₁ − 1 = 0 .
2. Dado que P ₁ ( x ) < 0 para x  = ⁠ 1 / 2 ⁠ , y P ₁ ( x ) > 0 para todo x > 1 , la raíz de P ₁ se encuentra entre ⁠ 1 / 2 ⁠ y 1, y el primer término en su expansión voraz (el segundo término en la expansión voraz para la proporción áurea) es ⁠ 1 / 2 ⁠ . Si x ₂ es la fracción restante después de este paso de la expansión voraz, satisface la ecuación P ₁ ( x ₂ + ⁠ 1 / 2 ⁠ ) = 0 , que se puede expandir como P ₂ ( x ₂ ) = 4 x ² ₂ + 8 x ₂ − 1 = 0 . 
3. Dado que P ₂ ( x ) < 0 para x  = ⁠ 1 / 9 ⁠ , y P ₂ ( x ) > 0 para todo x > ⁠ 1 / 8 ⁠ , el siguiente término en la expansión voraz es ⁠ 1 / 9 ⁠ . Si x ₃ es la fracción restante después de este paso de la expansión voraz, satisface la ecuación P ₂ ( x ₃ + ⁠ 1 / 9 ⁠ ) = 0 , que nuevamente puede expandirse como una ecuación polinómica con coeficientes enteros, P ₃ ( x ₃ ) = 324 x ² ₃ + 720 x ₃ − 5 = 0 . 

Continuar con este proceso de aproximación eventualmente produce la expansión voraz para la proporción áurea,

${\displaystyle \varphi ={\frac {1}{1}}+{\frac {1}{2}}+{\frac {1}{9}}+{\frac {1}{145}}+{\frac {1}{37986}}+\cdots }$(secuencia A117116 en el OEIS ).

La longitud, el denominador mínimo y el denominador máximo de la expansión voraz para todas las fracciones con numeradores y denominadores pequeños se pueden encontrar en la Enciclopedia en Línea de Secuencias de Enteros como las secuencias OEIS : A050205  , OEIS : A050206  y OEIS : A050210  , respectivamente. Además, la expansión voraz de cualquier número irracional conduce a una secuencia creciente infinita de enteros , y la OEIS contiene expansiones de varias constantes bien conocidas . Algunas entradas adicionales en la OEIS , aunque no están etiquetadas como producidas por el algoritmo voraz, parecen ser del mismo tipo.

En general, si se desea una expansión de fracciones egipcias en la que los denominadores estén restringidos de alguna manera, es posible definir un algoritmo voraz en el que en cada paso se elige la expansión. $${\displaystyle {\frac {x}{y}}={\frac {1}{d}}+{\frac {xd-y}{yd}},}$$ dónde${\displaystyle d}$se elige, entre todos los valores posibles que satisfacen las restricciones, lo más pequeño posible de tal manera que${\displaystyle xd>y}$y tal que${\displaystyle d}$es distinto de todos los denominadores elegidos previamente. Ejemplos de métodos definidos de esta manera incluyen la expansión de Engel , en la que cada denominador sucesivo debe ser un múltiplo del anterior, y la expansión voraz impar , en la que todos los denominadores están restringidos a ser números impares.

Sin embargo, puede resultar difícil determinar si un algoritmo de este tipo siempre logra encontrar una expansión finita. En particular, se desconoce si la expansión voraz impar termina con una expansión finita para todas las fracciones.${\displaystyle x/y}$para qué${\displaystyle y}$Es extraño, aunque es posible encontrar expansiones impares finitas para estas fracciones mediante métodos no voraces.