Ver o código fonte de «Algoritmo cobizoso para fraccións exipcias»

{{unsolved|matemáticas|Todo [[número racional]] cun denominador impar ten unha expansión cobizosa impar?}}
En [[matemáticas]], o '''algoritmo cobizoso para fraccións exipcias''' é un [[algoritmo cobizoso]], descrito por primeira vez por [[Leonardo Fibonacci|Fibonacci]], para transformar [[número racional |números racionais]] en [[fracción exipcia|fraccións exipcias]]. Unha fracción exipcia é unha representación dunha [[fracción irredutible]] como unha suma de [[fracción unitaria | fraccións unitarias]] distintas, como {{nowrap|1={{sfrac|5|6}} = {{sfrac|1 |2}} + {{sfrac|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 Fibonacci|Leonardo de Pisa]] (Fibonacci).{{sfn|Sigler|2002}} 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.<ref>{{harvnb|Sigler|2002}}, capítulo II.7</ref> 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 {{harvtxt|authorlink=James Joseph Sylvester|last=Sylvester| primeiro = J. J.|year=1880|James Joseph Sylvester}}<ref>Consulte, por exemplo, {{harvtxt|Cahen|1891}} e {{harvtxt|Spiess|1907}}.</ref> 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 {{harvtxt|Lambert|1770}}.

A expansión producida por este método para un número <math>x</math> chámase '''expansión exipcia cobizosa''', '''expansión de Sylvester''' ou '''expansión de Fibonacci–Sylvester''' de <math>x</math>. 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 [[Sucesión de Fibonacci|números de Fibonacci]].

==Algoritmo e exemplos==
O algoritmo de Fibonacci expande a fracción <math>x/y</math>, realizando repetidamente a substitución
<math display=block>\frac{x}{y}=\frac{1}{\lceil \frac y x \rceil}+\frac{(-y)\bmod x}{y \lceil \frac y x  \rceil}</math>
(simplificando o segundo termo desta substitución se é necesario). Por exemplo:
<math display=block>\frac{7}{15}=\frac{1}{3}+\frac{2}{15}=\frac{1}{3}+\frac{1}{8} +\frac{1}{120}.</math>
nesta expansión, o denominador 3 da primeira fracción unitaria é o resultado de redondear {{sfrac|15|7}} ata o seguinte número enteiro maior, e a fracción restante {{sfrac|2|15}} é o resultado de simplificar {{sfrac|−15 mod 7|15 × 3}} = {{sfrac|-1 mod 7|45}}= {{sfrac|6|45}}. O denominador da segunda fracción unitaria, 8, é o resultado de redondear {{sfrac| 15|2}} ata o seguinte número enteiro maior, e a fracción restante {{sfrac|1|120}} é o que falta de {{sfrac|7|15}} despois de restar tanto {{sfrac|1|3}} como {{sfrac|1|8}}.

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
<math display=block>\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},</math>
mentres que outros métodos conducen á estoutra expansión moito mellor
<math display=block>\frac{5}{121}=\frac{1}{33}+\frac{1}{121}+\frac{1}{363}.</math>
{{harvtxt|Wagon|1991}} suxire un exemplo que se comporta peor aínda, {{sfrac|31|311}}. O método cobizoso leva a unha expansión con dez termos, o último dos cales ten máis de 500 díxitos no seu denominador; porén, {{sfrac|31|311}} ten unha representación non cobizosa moito máis curta, {{nowrap|{{sfrac|1|12}} + {{sfrac|1|63}} + {{sfrac|1| 2799}} + {{sfrac|1|8708}}}}.

==Secuencia de Sylvester e aproximación máis próxima==
A [[Secuencia de Sylvester]] 2, 3, 7, 43, 1807, ... ({{OEIS|id=A000058}}) 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 <math> \lfloor \frac{y}{x}+ 1 \rfloor </math>  en lugar de <math> \lceil \frac{y}{x} \rceil </math>. Truncando esta secuencia a ''k'' termos e formando a fracción exipcia correspondente, p. ex. (para ''k''&nbsp;=&nbsp;4)
<math display=block>\frac12+\frac13+\frac17+\frac1{43}=\frac{1805}{1806}</math>
dá como resultado a fracción máis próxima posible de 1 por parte de calquera fracción exipcia de ''k'' termos.<ref>{{harvnb|Curtiss|1922}}; {{harvnb|Soundararajan|2005}}</ref> É dicir, por exemplo, calquera fracción exipcia para un número no intervalo aberto ({{sfrac|1805|1806}},&nbsp;1) require polo menos cinco termos. {{harvtxt|Curtiss|1922}} describe unha aplicación destes resultados de aproximación máis próxima para acoutar inferiormente o número de divisores dun [[número perfecto]], mentres que {{harvtxt|Stong|1983}} describe aplicacións en [[teoría de grupos]].


==Máxima lonxitude das expansións e condicións de congruencia==
Calquera fracción {{sfrac|''x''|''y''}} require como máximo ''x'' termos na súa expansión cobizosa. {{harvtxt|Mays|1987}} e {{harvtxt|Freitag|Phillips|1999}} examinan as condicións nas que o método cobizoso produce unha expansión de {{sfrac|''x''|''y''}} con exactamente ''x'' termos; estes pódense describir en función de condicións de congruencias en ''y''.

* Toda fracción {{sfrac|1|''y''}} require un termo na súa expansión cobizosa; a fracción deste tipo máis simple é {{sfrac|1|1}}.
* Toda fracción {{sfrac|2|''y''}} require dous termos na súa expansión cobizosa se e só se {{nowrap|''y'' ≡ 1 (mod 2)}}; a fracción deste tipo máis simple é {{sfrac|2|3}}.
* Unha fracción {{sfrac|3|''y''}} require tres termos na súa expansión cobizosa se e só se {{nowrap|''y'' ≡ 1 (mod 6)}}, e daquela {{nowrap |1=−''y'' mod ''x'' = 2}} e temos unha fracción impar {{sfrac|''y''(''y'' + 2)|3}}, polo que a fracción que fica cun único paso da expansión cobizosa, <math display=block>\frac{(-y)\bmod x}{y\left\lceil \frac y x \right\rceil} = \frac2{\,\frac{y( y+2)}{3}\,}</math> está nos termos máis sinxelos. A fracción máis sinxela {{sfrac|3|''y''}} cunha expansión de tres termos é {{sfrac|3|7}}.
* Unha fracción {{sfrac|4|''y''}} require catro termos na súa expansión cobizosa se e só se {{nowrap|''y'' ≡ 1 ou 17 (mod 24)}}, e daquela o numerador {{nowrap|−''y'' mod ''x''}} da fracción restante é 3 e o denominador é {{nowrap|1 (mod 6)}}. A fracción máis sinxela {{sfrac|4|''y''}} cunha expansión de catro termos é {{sfrac|4|17}}. A [[conxectura de Erdős-Straus]] afirma que todas as fraccións {{sfrac|4|''y''}} teñen unha expansión con tres ou menos termos, pero cando {{nowrap|''y'' ≡ 1 ou 17 (mod 24)}} tales expansións deben atoparse por métodos distintos do algoritmo cobizoso, co caso {{nowrap|17 (mod 24)}} cuberto pola relación de congruencia {{nowrap|2 (mod 3)}} .

De xeito máis xeral, a secuencia de fraccións {{sfrac|''x''|''y''}} que teñen expansións cobizosas de  ''x''  termos e que teñen o menor denominador posible ''y'' para cada '' x'' son
<math>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</math> {{OEIS|id=A048860}}.

==Outras secuencias enteiras==
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 {{OEIS|id=A050205}}, {{OEIS|id=A050206}} e {{OEIS|id=A050210}}, 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<ref>{{Cita web|url=https://oeis.org/search?q=greedy-Egyptian-fraction-expansion|páxina-web=oeis.org|título=Denominators of greedy Egyptian fraction expansion of Pi - 3.|data-acceso=25 de febreiro de 2024|lingua=en|data-publicación=2024}}</ref>. Algunhas [http://oeis.org/search?q=Egyptian-fraction-for entradas adicionais no OEIS], aínda que non están etiquetadas como producidas polo algoritmo cobizoso, parecen ser do mesmo tipo.

==Expansións relacionadas==
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
<math display=block>\frac{x}{y}=\frac{1}{d}+\frac{xd-y}{yd},</math>
onde se escolle o máis pequeno <math>d</math>, de entre todos os valores posibles que satisfán as restricións,  de xeito que <math>xd > y</math> e de xeito que <math>d</math> sexa distinto de todos os denominadores escollidos previamente. Exemplos de métodos definidos deste xeito inclúen:
* a [[expansión de Engel]], na que cada denominador sucesivo debe ser múltiplo do anterior, e 
* a '''expansión cobizosa impar''', na que todos os denominadores están restrinxidos a ser números impares. Sexa <math>u</math> o menor número impar que sexa maior ou igual a <math>y/x</math>, incluímos a fracción <math>1/u</math> na expansión e continuamos do mesmo xeito (evitando usos repetidos da mesma [[fracción unitaria]]) coa fracción restante <math>x/y-1/u</math>. Por exemplo: {{math|4/23 {{=}} 1/7 + 1/33 + 1/1329 + 1/2353659.}}

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 <math>x/y</math> para as que <math>y</math> é impar, aínda que por outros métodos sabemos que atopamos expansións finitas.

==Notas==
{{reflist}}

== Véxase tamén ==

=== Bibliografía ===
{{refbegin|colwidth=30em}}
*{{cita libro
 | last = Cahen | first = E.
 | journal = Nouvelles Annales des Mathématiques | series = Ser. 3
 | pages = 508–514
 | title = Note sur un développement des quantités numériques, qui presente quelque analogie avec celui en fractions continues
 | volume = 10
 | year = 1891}}.
*{{cita libro
 | last = Curtiss | first = D. R. | authorlink = David Raymond Curtiss
 | doi = 10.2307/2299023
 | issue = 10
 | journal = [[American Mathematical Monthly]]
 | jstor = 2299023
 | pages = 380–387
 | title = On Kellogg's diophantine problem
 | volume = 29
 | year = 1922}}.
*{{cita libro
 | last1 = Freitag | first1 = H. T. | author1-link = Herta Freitag
 | last2 = Phillips | first2 = G. M.
 | contribution = Sylvester's algorithm and Fibonacci numbers
 | location = Dordrecht
 | mr = 1737669
 | pages = 155–163
 | publisher = Kluwer Acad. Publ.
 | title = Applications of Fibonacci numbers, Vol. 8 (Rochester, NY, 1998)
 | year = 1999}}.
*{{cita libro
 | last = Lambert | first = J. H. | author-link = Johann Heinrich Lambert
 | location = Berlin
 | pages = 99–104
 | publisher = Zweyter Theil
 | title = Beyträge zum Gebrauche der Mathematik und deren Anwendung
 | year = 1770}}.
*{{cita libro
 | last = Mays | first = Michael
 | journal = Journal of Combinatorial Mathematics and Combinatorial Computing
 | mr = 0888838
 | pages = 141–148
 | title = A worst case of the Fibonacci–Sylvester expansion
 | volume = 1
 | year = 1987}}.
*{{cita libro
 | last = Salzer | first = H. E.
 | doi = 10.2307/2305906
 | issue = 3
 | journal = [[American Mathematical Monthly]]
 | jstor = 2305906
 | mr = 0020339
 | pages = 135–142
 | title = The approximation of numbers as sums of reciprocals
 | volume = 54
 | year = 1947}}.
*{{cita libro
 | last = Salzer | first = H. E.
 | doi = 10.2307/2304960
 | issue = 6
 | journal = [[American Mathematical Monthly]]
 | jstor = 2304960
 | mr = 0025512
 | pages = 350–356
 | title = Further remarks on the approximation of numbers as sums of reciprocals
 | volume = 55
 | year = 1948}}.
*{{cita libro
 | last = Sigler | first = Laurence E. (trans.)
 | isbn = 0-387-95419-8
 | publisher = Springer-Verlag
 | title = Fibonacci's Liber Abaci
 | year = 2002}}.
*{{cita libro
 | last = Soundararajan | first = K.
 | arxiv = math.CA/0502247
 | title = Approximating 1 from below using ''n'' Egyptian fractions
 | year = 2005}}.
*{{cita libro
 | last = Spiess | first = O.
 | journal = Archiv der Mathematik und Physik |series=Third Series
 | pages = 124–134
 | title = Über eine Klasse unendlicher Reihen
 | volume = 12
 | year = 1907}}.
*{{cita libro
 | last = Stong | first = R. E. | authorlink = Robert Evert Stong
 | doi = 10.1007/BF01455950
 | issue = 4
 | journal = Mathematische Annalen
 | mr = 0721884
 | pages = 501–512
 | title = Pseudofree actions and the greedy algorithm
 | volume = 265
 | year = 1983 }}.
*{{cita libro
 | last = Stratemeyer | first = G.
 | doi = 10.1007/BF01246446
 | journal = Mathematische Zeitschrift
 | pages = 767–768
 | title = Stammbruchentwickelungen für die Quadratwurzel aus einer rationalen Zahl
 | volume = 31
 | year = 1930| 
 }}.
*{{cita libro
 | last = Sylvester | first = J. J. | author-link = J. J. Sylvester
 | doi = 10.2307/2369261
 | issue = 4
 | journal = [[American Journal of Mathematics]]
 | jstor = 2369261
 | pages = 332–335
 | title = On a point in the theory of vulgar fractions
 | volume = 3
 | year = 1880}}.
*{{cita libro
 | last = Wagon | first = S. | authorlink = Stan Wagon
 | pages = [https://archive.org/details/mathematicainact0000wago/page/271 271]–277
 | publisher = W. H. Freeman
 | title = Mathematica in Action
 | url = https://archive.org/details/mathematicainact0000wago | year = 1991}}.
{{refend}}

{{Control de autoridades}}

[[Categoría:Aritmética]]
[[Categoría:Algoritmos]]