Algoritmo codicioso para fracciones egipcias

El algoritmo voraz para fracciones egipcias es un algoritmo voraz que convierte números racionales en fracciones egipcias , eligiendo en cada paso la alícuota más grande posible que se puede usar en la fracción residual.

La descomposición obtenida por un algoritmo codicioso para el número se denomina descomposición egipcia codiciosa, descomposición de Sylvester o descomposición del número de Fibonacci-Sylvester . $X$ $X$

Historia

Entre varios métodos diferentes para construir fracciones egipcias dados por Fibonacci en el Libro del ábaco , se encontraba un algoritmo codicioso, que se sugirió que se usara solo si fallaban otros métodos [1] . Posteriormente, el algoritmo codicioso y sus extensiones para aproximar números irracionales fueron redescubiertos varias veces, siendo el caso más antiguo y famoso el algoritmo de Sylvester [2] [3] . Un método que da la aproximación más cercana en cada paso, para el cual se permiten fracciones negativas, pertenece a Lambert [4] .

Algoritmo y ejemplos

El algoritmo de Fibonacci realiza la descomposición por reemplazo secuencial: $x/y$

{\frac {x}{y}}={\frac {1}{\lceil y/x\rceil }}+{\frac {(-y){\bmod x}}{y\lceil y/x\ rceil}}

(simplificando el segundo término si es necesario). Por ejemplo:

{\frac {7}{15}}={\frac {1}{3}}+{\frac {2}{15}}={\frac {1}{3}}+{\frac {1} {8}}+{\ fracción {1}{120}}

En esta expansión, el denominador de la primera alícuota es el resultado de redondear al siguiente número entero (mayor), y el resto es el resultado de la reducción . El divisor de la segunda fracción - , - es el resultado de redondear al siguiente número entero (mayor), y el resto es lo que queda después de restar y . $3$ $15/7$ $2/15$ $(-15{\pmod 7})/(15\cdot 3)=6/45$ $ocho$ $15/2$ $1/120$ $7/15$ $1/3$ $1/8$

Debido a que cada paso de expansión disminuye el numerador del resto, este método se completará en un número finito de pasos. Sin embargo, en comparación con los métodos de descomposición del antiguo Egipto o con métodos más modernos, este método puede generar una descomposición con denominadores bastante grandes. Por ejemplo, la expansión codiciosa de un número : $5/121$

{\frac {1}{25}}+{\frac {1}{757}}+{\frac {1}{763309}}+{\frac {1}{873960180913}}+{\frac {1} {1527612795642093418846225}}

mientras que otros métodos dan una expansión mucho más simple:

{\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}

y para el algoritmo voraz, da una expansión en diez fracciones, la última de las cuales tiene 500 dígitos en el denominador, mientras que hay una representación [5] : $31/311$

{\frac 1{12}}+{\frac 1{63}}+{\frac 1{2799}}+{\frac 1{8708}}

Secuencia de Sylvester

La secuencia de Sylvester se puede representar como formada por la expansión infinita de la unidad por medio de un algoritmo codicioso, donde en cada paso se elige un denominador en lugar de . Si cortamos esta secuencia por términos y formamos la fracción egipcia correspondiente, por ejemplo, para : $2,3,7,43,1807,\puntos$ $\lpiso y/x\rpiso +1$ $\lceil y/x\rceil$ $k$ $k = 4$

{\frac 12}+{\frac 13}+{\frac 17}+{\frac 1{43}}={\frac {1805}{1806}}

entonces obtenemos la aproximación más cercana a desde abajo entre las fracciones egipcias con miembros [6] [7] . Por ejemplo, cualquier fracción egipcia requiere al menos cinco términos para un número en un rango abierto . Se describe la aplicación de dichas expansiones más cercanas para una estimación más baja del número de divisores de un número perfecto [6] , así como en la teoría de grupos [8] . $una$ $k$ $(1805/1806.1)$

Expansiones de longitud máxima y condiciones de módulo

Cualquier fracción da los términos máximos en el algoritmo codicioso. Se investigan las condiciones bajo las cuales la expansión requiere exactamente fracciones [9] [10] , estas condiciones se pueden describir en términos de comparaciones de módulos: $x/y$ $X$ $x/y$ $X$ $y$

cualquier fracción conduce a un término en la expansión, la fracción más simple es ; $1/año$ $1/1$
cualquier fracción de la forma impar requiere dos términos en la expansión, la fracción más simple es ; $2/año$ $y>1$ $2/3$
en la expansión de una fracción , se necesitan tres términos si y solo si , en este caso, y es impar, por lo que el resto de la expansión después del primer paso: $3/año$ $y\equiv 1{\pmod 6}$ $y=2{\pmod x}$ $y(y+2)/3$ ${\frac {(-y){\bmod x}}{y\lceil y/x\rceil }}={\frac 2{y(y+2)/3}}$ irreducible, la fracción más simple de la forma , dando una expansión con tres miembros - ; $3/año$ $3/7$
la expansión de una fracción da cuatro términos si y sólo si o . En estos casos, el numerador de la fracción residual es igual y el denominador es comparable a . La fracción más simple de la especie con cuatro términos de expansión es , la conjetura de Erdős-Strauss establece que todas las fracciones de la especie tienen una descomposición con tres o menos términos, pero tales expansiones deben buscarse por métodos distintos al algoritmo codicioso. $4/año$ $y\equiv 1{\pmod {24}}$ $y\equiv 17{\pmod {24}}$ $y{\bmod x}$ $3$ $1{\pmod 6}$ $4/año$ $4/17$ $4/año$ $y\equiv 1{\pmod 2}4$ $y\equiv 17{\pmod 2}4$

En el caso general, la secuencia de fracciones con el mínimo denominador , que tiene expansión por un algoritmo voraz con miembros [11] : $x/y$ $y$ $X$

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)),\puntos

Cálculo aproximado de las raíces de polinomios

Existe un método para el cálculo aproximado de las raíces de un polinomio basado en el algoritmo voraz [12] [13] que determina la descomposición voraz de la raíz. En cada paso, se forma un polinomio adicional, que tiene el resto de la expansión como raíz. Por ejemplo, para calcular la expansión codiciosa de la sección áurea como una de las dos soluciones de la ecuación , el algoritmo realiza los siguientes pasos. $P_{0}(x)=x^{2}-x-1=0$

Como para y para todos , la raíz debe estar entre y . Por lo tanto, el primer término de la expansión es . Si es el resto después del primer paso de la expansión codiciosa, se debe satisfacer la ecuación , que se puede convertir a . $P_{0}(x)<0$ $x=1$ $P_{0}(x)>0$ $x\geqslant 2$ $P_{0}(x)$ $una$ $2$ $1/1$ $x_{1}$ $P_{0}(x_{1}+1)=0$ $P_{1}(x_{1})=x_{1}^{2}+x_{1}-1=0$
Como para y para todos , la raíz se encuentra entre y , el primer término de la expansión (el segundo término de la expansión de la sección áurea) es . Si es el resto después de este paso de expansión codicioso, satisface la ecuación , que se puede convertir a . $P_{1}(x)<0$ $x=1/2$ $P_{1}(x)>0$ $x>1$ $P_1$ $1/2$ $una$ $x_{1}$ $1/2$ $x_{2}$ $P_{1}(x_{2}+1/2)=0$ $P_{2}(x_{2})=4x_{2}^{2}+8x_{2}-1=0$
Como por y para todos , el próximo término en la expansión es . Si es el resto después de este paso de expansión codicioso, satisface la ecuación , que se puede convertir en una ecuación con coeficientes enteros . $P_{2}(x)<0$ $x=1/9$ $P_{2}(x)>0$ $x>1/8$ $1/9$ $x_{3}$ $P_{2}(x_{3}+1/9)=0$ $P_{3}(x_{3})=324x_{3}^{2}+720x_{3}-5=0$

Continuando este proceso de aproximación, se obtiene la expansión de la sección áurea en una fracción egipcia [14] :

\varphi ={\frac 11}+{\frac 12}+{\frac 19}+{\frac 1{145}}+{\frac 1{37986}}+\cdots

Otras secuencias enteras

La longitud, el denominador mínimo y el denominador máximo de la expansión codiciosa para fracciones con numeradores y denominadores pequeños se incluyen en la Encyclopedia of Integer Sequences [15] . Además, la expansión codiciosa de cualquier número irracional conduce a una secuencia infinitamente creciente de enteros, y OEIS contiene expansiones de algunas constantes bien conocidas.

Expansiones relacionadas

Es posible definir un algoritmo voraz con algunas restricciones en el denominador:

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

donde se elige entre todos los valores que satisfacen las restricciones impuestas y tienen el menor valor posible, en cuál y tal que difiere de todos los denominadores anteriores. Por ejemplo, la descomposición de Engel puede pensarse como un algoritmo de este tipo, en el que cada denominador admisible debe obtenerse multiplicando el anterior por algún número entero. Sin embargo, a menudo no es trivial establecer si dicho algoritmo siempre conduce a una descomposición finita. En particular , la expansión codiciosa impar de una fracción está formada por un algoritmo codicioso con una restricción en los denominadores impares. Se sabe que para impar hay una expansión en una fracción egipcia en la que todos los denominadores son impares, pero se desconoce si un algoritmo codicioso impar siempre conducirá a una expansión finita. $d$ $xd>y$ $d$ $x/y$ $y$

Notas

↑ Sigler, 2002 , capítulo II.7
↑ Silvestre, 1880 .
↑ Cahen, 1891 .
↑ Lamberto, 1770 .
↑ Vagón, 1991 .
↑ 12 Curtiss , 1922 .
↑ Soundarjan, 2005 .
↑ Fuerte, 1983 .
↑ Mayo, 1987 .
↑ Freitag, Phillips, 1999 .
↑ Secuencia OEIS A048860 _
↑ Stratemeyer, 1930 .
↑ Salzer, 1947 .
↑ Secuencia OEIS A117116 _
↑ A050205 , A050206 , A050210

Literatura

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