Algoritmo codicioso para fracciones egipcias - Greedy algorithm for Egyptian fractions

En matemáticas , el algoritmo codicioso para las fracciones egipcias es un algoritmo codicioso , 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 una 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 describe en el Liber Abaci ( 1202 ) de Leonardo de Pisa (Fibonacci). Se llama algoritmo codicioso porque en cada paso el algoritmo elige codiciosamente la fracción unitaria más grande 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 ( Sigler 2002 , capítulo II.7). Incluye el método codicioso como último recurso para situaciones en las que fallan varios métodos más simples; consulte la fracción egipcia para obtener una lista más detallada de estos métodos. Como detalla Salzer (1948), el método codicioso y sus extensiones para la aproximación de números irracionales han sido redescubiertos varias veces por los matemáticos modernos, la primera y más notablemente por JJ Sylvester  ( 1880 ); véanse, por ejemplo, Cahen (1891) y Spiess (1907) . 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 se remonta a Lambert (1770) .

La expansión producida por este método para un número x se denomina expansión egipcia codiciosa , expansión de Sylvester o expansión de Fibonacci-Sylvester de 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 .

Algoritmo y ejemplos

El algoritmo de Fibonacci expande la fracción X/y 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 este reemplazo 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 del redondeo 15/7 hasta el siguiente entero más grande, 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 del redondeo15/2 hasta el siguiente entero más grande, y la fracción restante 1/120 es lo que queda de 7/15 después de restar ambos 1/3 y 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 se 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 peor comportado,31/311. El método codicioso 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 codiciosa mucho más corta, 1/12 + 1/63 + 1/2799 + 1/8708.

Secuencia de Sylvester y aproximación más cercana

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⌉ . Truncar esta secuencia en k términos y formar la fracción egipcia correspondiente, p. Ej. (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 término k ( Curtiss 1922 ; Soundararajan 2005 ). 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 el límite inferior del número de divisores de un número perfecto , mientras que Stong (1983) describe aplicaciones en la teoría de grupos .

Expansiones de longitud máxima y condiciones de congruencia

Cualquier fracción X/yrequiere como máximo x términos en su expansión codiciosa. Mays (1987) y Freitag y Phillips (1999) examinan las condiciones bajo las cuales el método codicioso produce una expansión deX/ycon exactamente x términos; estos pueden describirse en términos de condiciones de congruencia en y .

• Cada fracción 1/yrequiere un término en su codiciosa expansión; la fracción más simple es1/1.
• Cada fracción 2/yrequiere dos términos en su expansión codiciosa si y solo si y ≡ 1 (mod 2) ; la fracción más simple es2/3.
• Una fracción 3/yrequiere tres términos en su expansión codiciosa si y solo si y ≡ 1 (mod 6) , para entonces - y mod x = 2 yy ( y + 2)/3 es impar, por lo que la fracción que queda después de un solo paso de la expansión codiciosa,

${\ Displaystyle {\ frac {(-y) {\ bmod {x}}} {y \ left \ lceil {\ frac {y} {x}} \ right \ rceil}} = {\ frac {2} {\ , {\ frac {y (y + 2)} {3}} \,}}}$

es en términos más simples. La fracción más simple3/y con una expansión de tres términos es 3/7.

• Una fracción 4/yrequiere cuatro términos en su expansión codiciosa si y solo si y ≡ 1 o 17 (mod 24) , porque 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 simple4/y con una expansión de cuatro términos es 4/17. La conjetura de Erdős-Straus establece que todas las fracciones4/ytienen una expansión con tres o menos términos, pero cuando y ≡ 1 o 17 (mod 24) tales expansiones deben ser encontradas por métodos distintos al algoritmo codicioso, con el caso 17 (mod 24) cubierto por la relación de congruencia 2 (mod 3) .

De manera más general, la secuencia de fracciones X/yque tienen expansiones codiciosas de término x y que tienen el denominador más pequeño posible y 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 la OEIS ).

Aproximación de raíces polinomiales

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 codicioso. Su algoritmo calcula la expansión codiciosa de una raíz; en cada paso de esta expansión mantiene un polinomio auxiliar que tiene como raíz la fracción restante a expandir. Considere como ejemplo la aplicación de este método para encontrar la expansión codiciosa de la proporción áurea , una de las dos soluciones de la ecuación polinomial 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 codiciosa de la proporción áurea es1/1. Si x ₁ es la fracción restante después del primer paso de la expansión codiciosa, 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 _{1 se} encuentra entre1/2 y 1, y el primer término en su expansión codiciosa (el segundo término en la expansión codiciosa de la proporción áurea) es 1/2. Si x ₂ es la fracción restante después de este paso de la expansión codiciosa, satisface la ecuación P ₁ ( x ₂ +1/2) = 0 , que se puede expandir como P ₂ ( x ₂ ) = 4 x²
   ₂+ 8 x _2-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 de la expansión codiciosa es 1/9. Si x ₃ es la fracción restante después de este paso de la expansión codiciosa, satisface la ecuación P ₂ ( x ₃ +1/9) = 0 , que nuevamente se puede expandir como una ecuación polinomial con coeficientes enteros, P ₃ ( x ₃ ) = 324 x²
   ₃+ 720 x ₃ - 5 = 0 .

Continuar con este proceso de aproximación eventualmente produce la expansión codiciosa de 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 la OEIS ).

Otras secuencias de enteros

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

Expansiones relacionadas

En general, si uno quiere una expansión de fracción egipcia en la que los denominadores están restringidos de alguna manera, es posible definir un algoritmo codicioso en el que en cada paso se elige la expansión

${\ Displaystyle {\ frac {x} {y}} = {\ frac {1} {d}} + {\ frac {xd-y} {yd}},}$

donde d se elige, entre todos los valores posibles que satisfacen las restricciones, tan pequeño como sea posible, de modo que xd  >  y y tal que d sea ​​distinto de todos los denominadores elegidos previamente. Por ejemplo, la expansión de Engel puede verse como un algoritmo de este tipo en el que cada denominador sucesivo debe ser un múltiplo del anterior. Sin embargo, puede ser difícil determinar si un algoritmo de este tipo siempre puede tener éxito en encontrar una expansión finita. En particular, la extraña expansión codiciosa de una fracciónX/yestá formado por un algoritmo codicioso de este tipo en el que todos los denominadores están restringidos a números impares; se sabe que, siempre que y es impar, hay una expansión de fracción egipcia finita en la que todos los denominadores son impares, pero no se sabe si la expansión codiciosa impar es siempre finita.

Referencias