Algoritmo cobizoso para fraccións exipcias
En matemáticas, o algoritmo cobizoso para fraccións exipcias é un algoritmo cobizoso, descrito por primeira vez por Fibonacci, para transformar números racionais en fraccións exipcias. Unha fracción exipcia é unha representación dunha fracción irredutible como unha suma de fraccións unitarias distintas, como 5/6 = 1/2 + 1/3. Como o nome indica, estas representacións usáronse desde hai moito tempo no antigo Exipto, mais o primeiro método sistemático publicado para construír tales expansións foi descrito en 1202 no Liber Abaci de Leonardo de Pisa (Fibonacci).[1] Chámase algoritmo cobizoso porque en cada paso o algoritmo elixe cobizosamente a fracción unitaria máis grande posible que se pode usar en calquera representación da fracción restante.
En realidade, Fibonacci enumera varios métodos diferentes para construír representacións de fraccións exipcias.[2] Inclúe o método cobizoso como último recurso para situacións nas que fallan varios métodos máis sinxelos; vexa Fracción exipcia para unha lista máis detallada destes métodos. Como detalla Salzer (1948), o método cobizoso, e as súas extensións para a aproximación de números irracionais, foron redescubertos varias veces polos matemáticos modernos, o máis antigo e máis notable foi James Joseph Sylvester[3] Un método de expansión moi relacionado que produce aproximacións máis próximas en cada paso ao permitir que algunhas fraccións unitarias da suma sexan negativas remóntase a Lambert (1770).
A expansión producida por este método para un número chámase expansión exipcia cobizosa, expansión de Sylvester ou expansión de Fibonacci–Sylvester de . Porén, o termo expansión de Fibonacci adoita referirse, non a este método, senón á representación de números enteiros como sumas de números de Fibonacci.
Algoritmo e exemplos editar
O algoritmo de Fibonacci expande a fracción , realizando repetidamente a substitución
Como cada paso da expansión reduce o numerador da fracción restante a expandir, este método sempre remata cunha expansión finita; no entanto, en comparación coas expansións exipcias antigas ou con métodos máis modernos, este método pode producir expansións bastante longas, con grandes denominadores. Por exemplo, este método expande
Secuencia de Sylvester e aproximación máis próxima editar
A Secuencia de Sylvester 2, 3, 7, 43, 1807, ... ((secuencia A000058 na OEIS)) pódese ver como unha secuencia xerada por unha expansión cobizosa infinita deste tipo para o número 1, onde en cada paso escollemos o denominador en lugar de . Truncando esta secuencia a k termos e formando a fracción exipcia correspondente, p. ex. (para k = 4)
Máxima lonxitude das expansións e condicións de congruencia editar
Calquera fracción x/y require como máximo x termos na súa expansión cobizosa. Mays (1987) e Freitag & Phillips (1999) examinan as condicións nas que o método cobizoso produce unha expansión de x/y con exactamente x termos; estes pódense describir en función de condicións de congruencias en y.
- Toda fracción 1/y require un termo na súa expansión cobizosa; a fracción deste tipo máis simple é 1/1.
- Toda fracción 2/y require dous termos na súa expansión cobizosa se e só se y ≡ 1 (mod 2); a fracción deste tipo máis simple é 2/3.
- Unha fracción 3/y require tres termos na súa expansión cobizosa se e só se y ≡ 1 (mod 6), e daquela −y mod x = 2 e temos unha fracción impar y(y + 2)/3, polo que a fracción que fica cun único paso da expansión cobizosa,
- Unha fracción 4/y require catro termos na súa expansión cobizosa se e só se y ≡ 1 ou 17 (mod 24), e daquela o numerador −y mod x da fracción restante é 3 e o denominador é 1 (mod 6). A fracción máis sinxela 4/y cunha expansión de catro termos é 4/17. A conxectura de Erdős-Straus afirma que todas as fraccións 4/y teñen unha expansión con tres ou menos termos, pero cando y ≡ 1 ou 17 (mod 24) tales expansións deben atoparse por métodos distintos do algoritmo cobizoso, co caso 17 (mod 24) cuberto pola relación de congruencia 2 (mod 3) .
De xeito máis xeral, a secuencia de fraccións x/y que teñen expansións cobizosas de x termos e que teñen o menor denominador posible y para cada x son (secuencia A048860 na OEIS).
Outras secuencias enteiras editar
A lonxitude, o denominador mínimo e o denominador máximo da expansión cobizosa para todas as fraccións con numeradores e denominadores pequenos pódense atopar na OEIS (Enciclopedia online de secuencias de enteiros) como secuencias (secuencia A050205 na OEIS), (secuencia A050206 na OEIS) e (secuencia A050210 na OEIS), respectivamente. Ademais, a expansión cobizosa de calquera número irracional leva a unha secuencia crecente infinita de números enteiros, e a OEIS contén expansións de varias constantes coñecidas[5]. Algunhas entradas adicionais no OEIS, aínda que non están etiquetadas como producidas polo algoritmo cobizoso, parecen ser do mesmo tipo.
Expansións relacionadas editar
En xeral, se se quere unha expansión de fracción exipcia na que os denominadores estean restrinxidos dalgún xeito, é posible definir un algoritmo cobizoso no que en cada paso se escolla a expansión
Non obstante, pode ser difícil determinar se un algoritmo deste tipo sempre pode ter éxito en atopar unha expansión finita. En particular, descoñécese se a expansión cobizosa impar termina cunha expansión finita para todas as fraccións para as que é impar, aínda que por outros métodos sabemos que atopamos expansións finitas.
Notas editar
- ↑ Sigler 2002.
- ↑ Sigler 2002, capítulo II.7
- ↑ Consulte, por exemplo, Cahen (1891) e Spiess (1907).
- ↑ Curtiss 1922; Soundararajan 2005
- ↑ "Denominators of greedy Egyptian fraction expansion of Pi - 3.". oeis.org (en inglés). 2024. Consultado o 25 de febreiro de 2024.
Véxase tamén editar
Bibliografía editar
- Cahen, E. (1891). Note sur un développement des quantités numériques, qui presente quelque analogie avec celui en fractions continues. Nouvelles Annales des Mathématiques. Ser. 3 10. pp. 508–514..
- Curtiss, D. R. (1922). On Kellogg's diophantine problem. American Mathematical Monthly 29. pp. 380–387. JSTOR 2299023. doi:10.2307/2299023..
- Freitag, H. T.; Phillips, G. M. (1999). "Sylvester's algorithm and Fibonacci numbers". Applications of Fibonacci numbers, Vol. 8 (Rochester, NY, 1998). Dordrecht: Kluwer Acad. Publ. pp. 155–163. MR 1737669..
- Lambert, J. H. (1770). Beyträge zum Gebrauche der Mathematik und deren Anwendung. Berlin: Zweyter Theil. pp. 99–104..
- Mays, Michael (1987). A worst case of the Fibonacci–Sylvester expansion. Journal of Combinatorial Mathematics and Combinatorial Computing 1. pp. 141–148. MR 0888838..
- Salzer, H. E. (1947). The approximation of numbers as sums of reciprocals. American Mathematical Monthly 54. pp. 135–142. JSTOR 2305906. MR 0020339. doi:10.2307/2305906..
- Salzer, H. E. (1948). Further remarks on the approximation of numbers as sums of reciprocals. American Mathematical Monthly 55. pp. 350–356. JSTOR 2304960. MR 0025512. doi:10.2307/2304960..
- Sigler, Laurence E. (trans.) (2002). Fibonacci's Liber Abaci. Springer-Verlag. ISBN 0-387-95419-8..
- Soundararajan, K. (2005). Approximating 1 from below using n Egyptian fractions. arXiv:math.CA/0502247..
- Spiess, O. (1907). Über eine Klasse unendlicher Reihen. Archiv der Mathematik und Physik. Third Series 12. pp. 124–134..
- Stong, R. E. (1983). Pseudofree actions and the greedy algorithm. Mathematische Annalen 265. pp. 501–512. MR 0721884. doi:10.1007/BF01455950..
- Stratemeyer, G. (1930). Stammbruchentwickelungen für die Quadratwurzel aus einer rationalen Zahl. Mathematische Zeitschrift 31. pp. 767–768. doi:10.1007/BF01246446..
- Sylvester, J. J. (1880). On a point in the theory of vulgar fractions. American Journal of Mathematics 3. pp. 332–335. JSTOR 2369261. doi:10.2307/2369261..
- Wagon, S. (1991). Mathematica in Action. W. H. Freeman. pp. 271–277..