Algoritmo voraz para fracciones egipcias

Método simple para encontrar 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 una suma de fracciones unitarias distintas , como ⁠5/6⁠ = ⁠1/2⁠ + ⁠1/3⁠ . Como indica el nombre, 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 vorazmente la fracción unitaria más grande posible que se puede utilizar en cualquier representación de la fracción restante.

Fibonacci 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. Como detalla Salzer (1948), el método voraz y sus extensiones para la aproximación de números irracionales han sido redescubiertos varias veces por matemáticos modernos, el primero y más notable fue JJ Sylvester  (1880) ^[3]. 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 que se produce con este método para un número se denomina expansión egipcia voraz , expansión de Sylvester o expansión de Fibonacci-Sylvester de . Sin embargo, el término expansión de Fibonacci no suele referirse a este método, sino a la representación de números enteros como sumas de números de Fibonacci . ${\displaystyle x}$ ${\displaystyle x}$

Algoritmo y ejemplos

El algoritmo de Fibonacci expande la fracción a representar, realizando repetidamente el reemplazo (simplificando el segundo término en este reemplazo según sea necesario). Por ejemplo: en esta expansión, el denominador 3 de la primera fracción unitaria es el resultado del redondeo ⁠ ${\displaystyle x/y}$ $${\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 }}}$$ $${\displaystyle {\frac {7}{15}}={\frac {1}{3}}+{\frac {2}{15}}={\frac {1}{3}}+{\frac {1}{8}}+{\frac {1}{120}}.}$$15/7⁠ hasta el siguiente entero mayor, y la fracción restante ⁠2/15⁠ es el resultado de simplificar ⁠-15 módulo 7/15 × 3⁠  =  ⁠6/45⁠ . El denominador de la segunda fracción unitaria, 8, es el resultado del redondeo .15/2⁠ hasta el siguiente entero mayor, 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 que son bastante largas, con denominadores grandes. Por ejemplo, este método expande mientras que otros métodos conducen a una expansión mucho mejor. Wagon (1991) sugiere un ejemplo aún peor, ⁠ $${\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}},}$$ $${\displaystyle {\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}.}$$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 codiciosa mucho más corta, ⁠1/12⁠ + ⁠1/63⁠ + ⁠1/2799⁠ + ⁠1/8708⁠ .

Sucesión de Sylvester y aproximación más cercana

La secuencia de Silvestre 2, 3, 7, 43, 1807, ... ( OEIS : A000058 ) puede verse como generada por una expansión infinita y voraz de este tipo para el número 1, donde en cada paso elegimos el denominador ⌊ ⁠y/incógnita⁠ ⌋ + 1 en lugar de ⌈ ⁠y/incógnita⁠ ⌉ . Truncando esta secuencia a k términos y formando la fracción egipcia correspondiente, p. ej. (para k  = 4) se obtiene la subestimación más cercana posible de 1 por cualquier fracción egipcia de k términos. ^[4] Es decir, por ejemplo, cualquier fracción egipcia para un número en el intervalo abierto ( ⁠ $${\displaystyle {\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}={\frac {1805}{1806}}}$$1805/18061) requiere al menos cinco términos. Curtiss (1922) describe una aplicación de estos resultados de aproximación más cercana para limitar inferiormente el 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ónincógnita/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 ⁠incógnita/y⁠ con exactamente x términos; estos pueden describirse en términos de condiciones de congruencia en y .

• Cada fracción1/y⁠ requiere un término en su expansión codiciosa; la fracción más simple de este tipo es ⁠1/1⁠ .
• Cada fracción2/y⁠ requiere dos términos en su expansión codiciosa si y solo si y ≡ 1 (mod 2) ; la fracción más simple de este tipo es ⁠2/3⁠ .
• Una fracción3/y⁠ requiere tres términos en su expansión codiciosa si y solo si y ≡ 1 (mod 6) , 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, es en términos más simples. La fracción más simple ⁠ $${\displaystyle {\frac {(-y){\bmod {x}}}{y\left\lceil {\frac {y}{x}}\right\rceil }}={\frac {2}{\,{\frac {y(y+2)}{3}}\,}}}$$3/y⁠ con una expansión de tres términos es ⁠3/7⁠ .
• Una fracción4/y⁠ requiere cuatro términos en su expansión voraz 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 simple ⁠4/y⁠ con una expansión de cuatro términos es ⁠4/17⁠ . La conjetura de Erdős-Straus establece que todas las fracciones ⁠4/y⁠ tienen una expansión con tres o menos términos, pero cuando y ≡ 1 o 17 (mod 24) dichas expansiones deben encontrarse mediante métodos distintos al algoritmo voraz, estando el caso 17 (mod 24) cubierto por la relación de congruencia 2 (mod 3) .

De manera más general, la secuencia de fraccionesincógnita/y⁠ que tienen expansiones voraces de términos x 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 la OEIS ).

Aproximación de raíces polinómicas

Stratemeyer (1930) y Salzer (1947) describen un método para encontrar una aproximación precisa para 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 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 voraz de la proporció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 codiciosa de la proporció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 puede expandirse 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 codiciosa (el segundo término en la expansión codiciosa 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 puede expandirse 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 codiciosa 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 puede expandirse nuevamente como una ecuación polinómica con coeficientes enteros, P ₃ ( x ₃ ) = 324 x²
   ₃+ 720 x ₃ − 5 = 0 .

Continuar con este proceso de aproximación produce eventualmente 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 números enteros

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 números enteros como secuencias OEIS : A050205 , OEIS : A050206 y OEIS : A050210 , respectivamente. Además, la expansión voraz de cualquier número irracional conduce a una secuencia infinita creciente de números 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.

Expansiones relacionadas

En general, si se desea una expansión de fracción egipcia 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 donde se elige, entre todos los valores posibles que satisfacen las restricciones, lo más pequeño posible tal que y tal que sea 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. $${\displaystyle {\frac {x}{y}}={\frac {1}{d}}+{\frac {xd-y}{yd}},}$$ ${\displaystyle d}$ ${\displaystyle xd>y}$ ${\displaystyle d}$

Sin embargo, puede resultar difícil determinar si un algoritmo de este tipo siempre puede 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 para las que es impar, aunque es posible encontrar expansiones impares finitas para estas fracciones mediante métodos no voraces. ${\displaystyle x/y}$ ${\displaystyle y}$

Notas

1. Sigler 2002.
2. Sigler 2002, capítulo II.7
3. Véase, por ejemplo, Cahen (1891) y Spiess (1907).
4. Curtiss 1922; Soundararajan 2005

Referencias

• Cahen, E. (1891), "Note sur un développement des quantités numériques, qui presente quelque analogie avec celui en fracciones continúa", Nouvelles Annales des Mathématiques , Ser. 3, 10 : 508–514.
• Curtiss, DR (1922), "Sobre el problema diofántico de Kellogg", American Mathematical Monthly , 29 (10): 380–387, doi :10.2307/2299023, JSTOR  2299023.
• Freitag, HT ; Phillips, GM (1999), "Algoritmo de Sylvester y números de Fibonacci", Aplicaciones de los números de Fibonacci, vol. 8 (Rochester, NY, 1998) , Dordrecht: Kluwer Acad. Publ., págs. 155–163, MR  1737669.
• Lambert, JH (1770), Beyträge zum Gebrauche der Mathematik und deren Anwendung , Berlín: Zweyter Theil, págs. 99-104.
• Mays, Michael (1987), "El peor caso de la expansión de Fibonacci-Sylvester", Journal of Combinatorial Mathematics and Combinatorial Computing , 1 : 141–148, MR  0888838.
• Salzer, HE (1947), "La aproximación de números como sumas de recíprocos", American Mathematical Monthly , 54 (3): 135–142, doi :10.2307/2305906, JSTOR  2305906, MR  0020339.
• Salzer, HE (1948), "Observaciones adicionales sobre la aproximación de números como sumas de recíprocos", American Mathematical Monthly , 55 (6): 350–356, doi :10.2307/2304960, JSTOR  2304960, MR  0025512.
• Sigler, Laurence E. (trad.) (2002), Liber Abaci de Fibonacci , Springer-Verlag, ISBN 0-387-95419-8.
• Soundararajan, K. (2005), Aproximación de 1 desde abajo usando n fracciones egipcias , arXiv : math.CA/0502247.
• Spiess, O. (1907), "Über eine Klasse unendlicher Reihen", Archiv der Mathematik und Physik , tercera serie, 12 : 124-134.
• Stong, RE (1983), "Acciones pseudolibres y el algoritmo codicioso", Mathematische Annalen , 265 (4): 501–512, doi :10.1007/BF01455950, MR  0721884, S2CID  120347233.
• Stratemeyer, G. (1930), "Stammbruchentwickelungen für die Quadratwurzel aus einer racionalen Zahl", Mathematische Zeitschrift , 31 : 767–768, doi :10.1007/BF01246446, S2CID  120956180.
• Sylvester, JJ (1880), "Sobre un punto en la teoría de fracciones vulgares", American Journal of Mathematics , 3 (4): 332–335, doi :10.2307/2369261, JSTOR  2369261.
• Wagon, S. (1991), Mathematica en acción , WH Freeman, págs. 271–277.