Algoritmo codicioso para fracciones egipcias

Método sencillo para encontrar fracciones egipcias.

En matemáticas , el algoritmo codicioso para 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 , como5/6=1/2+1/3. Como su nombre indica, estas representaciones se han utilizado ya en 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 codicioso porque en cada paso el algoritmo elige con avidez la fracción unitaria más grande posible que puede usarse en cualquier representación de la fracción restante.

En realidad, Fibonacci enumera varios métodos diferentes para construir representaciones de fracciones egipcias. ^[2] Incluye el método codicioso como último recurso para situaciones en las que varios métodos más simples fallan; 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 matemáticos modernos, el primero y más notablemente por 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 producida por este método para un número se llama expansión egipcia codiciosa , expansión de Sylvester o expansión de Fibonacci-Sylvester . Sin embargo, el término expansión de Fibonacci generalmente no se refiere 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 ${\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/72/15−15 módulo 7/15×36/4515/21/1207/151/31/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}},}$$

$${\displaystyle {\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}.}$$

31/31131/3111/12+1/63+1/2799+1/8708

Secuencia de Sylvester y máxima aproximación.

La secuencia de Sylvester 2, 3, 7, 43, 1807, ... ( OEIS : A000058 ) puede verse como generada por una expansión infinita y codiciosa 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 a k términos y formar 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}}}$$

de k términos. ^[4]1805/1806número perfectoteoría de grupos

Expansiones de longitud máxima y condiciones de congruencia.

cualquier fracciónX/yrequiere como máximo x términos en su codiciosa expansión. 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ón1/yrequiere un término en su codiciosa expansión; la fracción más simple es1/1.
• cada fracción2/yrequiere dos términos en su codiciosa expansión si y sólo si y ≡ 1 (mod 2) ; la fracción más simple es2/3.
• Una fracción3/yrequiere tres términos en su codiciosa expansión si y sólo si y ≡ 1 (mod 6) , para entonces − y mod x = 2 yy ( y + 2)/3es impar, por lo que la fracción restante 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/ycon una expansión de tres términos es3/7.
• Una fracción4/yrequiere cuatro términos en su codiciosa expansión si y sólo si y ≡ 1 o 17 (mod 24) , pues 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/ycon una expansión de cuatro términos es4/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) dichas expansiones deben encontrarse mediante métodos distintos al algoritmo codicioso, estando cubierto el caso 17 (mod 24) 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érminos x y que tienen el menor denominador 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 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 codiciosa expansión 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 ₁ se encuentra entre1/2y 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) es1/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 ₂ - 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 codiciosa expansión es1/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 polinómica con coeficientes enteros, P ₃ ( x ₃ ) = 324 x²
   ₃+ 720 x ₃ - 5 = 0 .

Continuar con este proceso de aproximación finalmente produce la codiciosa expansión 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 enteras

La longitud, el denominador mínimo y el denominador máximo 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 enteras 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 creciente infinita de números enteros, y el 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 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

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

la expansión de Engella expansión codiciosa impar ${\displaystyle d}$ ${\displaystyle xd>y}$ ${\displaystyle d}$

Sin embargo, puede resultar difícil determinar si un algoritmo de este tipo siempre puede lograr encontrar una expansión finita. En particular, se desconoce si la expansión impar codiciosa termina con una expansión finita para todas las fracciones para las cuales es impar, aunque es posible encontrar expansiones finitas impares para estas fracciones mediante métodos no codiciosos. ${\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), "El algoritmo de Sylvester y los números de Fibonacci", Aplicaciones de los números de Fibonacci, vol. 8 (Rochester, Nueva York, 1998) , Dordrecht: Kluwer Acad. Publ., págs. 155–163, SEÑOR  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), "Más comentarios 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 de la teoría de las 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.