Algoritmo cobizoso para fraccións exipcias

Modelo:Unsolved 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 Modelo:Nowrap. 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).Modelo:Sfn 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. 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 Modelo:Harvtxt 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 Modelo:Harvtxt.

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

O algoritmo de Fibonacci expande a fracción $x/y$, realizando repetidamente a substitución $$\frac{x}{y}=\frac{1}{\lceil \frac{y}{x}\rceil }+\frac{(-y)modx}{y\lceil \frac{y}{x}\rceil }$$ (simplificando o segundo termo desta substitución se é necesario). Por exemplo: $$\frac{7}{15}=\frac{1}{3}+\frac{2}{15}=\frac{1}{3}+\frac{1}{8}+\frac{1}{120}.$$ nesta expansión, o denominador 3 da primeira fracción unitaria é o resultado de redondear Modelo:Sfrac ata o seguinte número enteiro maior, e a fracción restante Modelo:Sfrac é o resultado de simplificar Modelo:Sfrac = Modelo:Sfrac= Modelo:Sfrac. O denominador da segunda fracción unitaria, 8, é o resultado de redondear Modelo:Sfrac ata o seguinte número enteiro maior, e a fracción restante Modelo:Sfrac é o que falta de Modelo:Sfrac despois de restar tanto Modelo:Sfrac como Modelo:Sfrac.

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 $$\frac{5}{121}=\frac{1}{25}+\frac{1}{757}+\frac{1}{763309}+\frac{1}{873960180913}+\frac{1}{1527612795642093418846225},$$ mentres que outros métodos conducen á estoutra expansión moito mellor $$\frac{5}{121}=\frac{1}{33}+\frac{1}{121}+\frac{1}{363}.$$ Modelo:Harvtxt suxire un exemplo que se comporta peor aínda, Modelo:Sfrac. 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, Modelo:Sfrac ten unha representación non cobizosa moito máis curta, Modelo:Nowrap.

Secuencia de Sylvester e aproximación máis próxima

A Secuencia de Sylvester 2, 3, 7, 43, 1807, ... (Modelo: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 $\lfloor \frac{y}{x}+1\rfloor$ en lugar de $\lceil \frac{y}{x}\rceil$. Truncando esta secuencia a k termos e formando a fracción exipcia correspondente, p. ex. (para k = 4) $$\frac{1}{2}+\frac{1}{3}+\frac{1}{7}+\frac{1}{43}=\frac{1805}{1806}$$ dá como resultado a fracción máis próxima posible de 1 por parte de calquera fracción exipcia de k termos. É dicir, por exemplo, calquera fracción exipcia para un número no intervalo aberto (Modelo:Sfrac, 1) require polo menos cinco termos. Modelo:Harvtxt 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 Modelo:Harvtxt describe aplicacións en teoría de grupos.

Máxima lonxitude das expansións e condicións de congruencia

Calquera fracción Modelo:Sfrac require como máximo x termos na súa expansión cobizosa. Modelo:Harvtxt e Modelo:Harvtxt examinan as condicións nas que o método cobizoso produce unha expansión de Modelo:Sfrac con exactamente x termos; estes pódense describir en función de condicións de congruencias en y.

• Toda fracción Modelo:Sfrac require un termo na súa expansión cobizosa; a fracción deste tipo máis simple é Modelo:Sfrac.
• Toda fracción Modelo:Sfrac require dous termos na súa expansión cobizosa se e só se Modelo:Nowrap; a fracción deste tipo máis simple é Modelo:Sfrac.
• Unha fracción Modelo:Sfrac require tres termos na súa expansión cobizosa se e só se Modelo:Nowrap, e daquela Modelo:Nowrap e temos unha fracción impar Modelo:Sfrac, polo que a fracción que fica cun único paso da expansión cobizosa, $$\frac{(-y)modx}{y\lceil \frac{y}{x}\rceil }=\frac{2}{\frac{y(y+2)}{3}}$$ está nos termos máis sinxelos. A fracción máis sinxela Modelo:Sfrac cunha expansión de tres termos é Modelo:Sfrac.
• Unha fracción Modelo:Sfrac require catro termos na súa expansión cobizosa se e só se Modelo:Nowrap, e daquela o numerador Modelo:Nowrap da fracción restante é 3 e o denominador é Modelo:Nowrap. A fracción máis sinxela Modelo:Sfrac cunha expansión de catro termos é Modelo:Sfrac. A conxectura de Erdős-Straus afirma que todas as fraccións Modelo:Sfrac teñen unha expansión con tres ou menos termos, pero cando Modelo:Nowrap tales expansións deben atoparse por métodos distintos do algoritmo cobizoso, co caso Modelo:Nowrap cuberto pola relación de congruencia Modelo:Nowrap .

De xeito máis xeral, a secuencia de fraccións Modelo:Sfrac que teñen expansións cobizosas de x termos e que teñen o menor denominador posible y para cada x son $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$ Modelo:OEIS.

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 Modelo:OEIS, Modelo:OEIS e Modelo: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. 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

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 $$\frac{x}{y}=\frac{1}{d}+\frac{xd-y}{yd},$$ onde se escolle o máis pequeno $d$, de entre todos os valores posibles que satisfán as restricións, de xeito que $xd>y$ e de xeito que $d$ 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 $u$ o menor número impar que sexa maior ou igual a $y/x$, incluímos a fracción $1/u$ na expansión e continuamos do mesmo xeito (evitando usos repetidos da mesma fracción unitaria) coa fracción restante $x/y-1/u$. Por exemplo: Modelo:Math

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

Véxase tamén

Bibliografía

• Modelo:Cita libro.
• Modelo:Cita libro.
• Modelo:Cita libro.
• Modelo:Cita libro.
• Modelo:Cita libro.
• Modelo:Cita libro.
• Modelo:Cita libro.
• Modelo:Cita libro.
• Modelo:Cita libro.
• Modelo:Cita libro.
• Modelo:Cita libro.
• Modelo:Cita libro.
• Modelo:Cita libro.
• Modelo:Cita libro.