Essa eh a chamada sequencia de Farey de ordem N (F(N)). a/b pertence a F(N) <==> 0 <= a <= b <= N e mdc(a,b) = 1.
Alem disso, se o k-esimo termo eh a/b e o (k+1)-esimo eh c/d entao: a/b < c/d e bc - ad = 1, ou seja: c/d = a/b + 1/(bd). Apesar de nao fornecer uma formula, o algoritmo abaixo (descrito em "An Introduction to the Theory of Numbers" - Hardy-Wright - sec. 3.4) permite determinar o c/d conhecendo-se a/b: Como mdc(a,b) =1, existem inteiros x e y tais que bx - ay = 1. Se (p,q) eh uma solucao particular dessa equacao diofantina (ou seja, bp - aq = 1) entao, a solucao geral serah: x = p + a*k y = q + b*k (k em Z) Podemos escolher k de modo que N - b < q + b*k = y <= N. Dessa forma, teremos uma solucao (x,y) tal que: mdc(x,y) = 1 e N - b < y <= N ==> x/y pertence a F(N) e x/y = a/b + 1/(by) > a/b. Vamos provar, por absurdo, que x/y = c/d. Suponhamos que x/y <> c/d. Entao, x/y > c/d ==> x/y - c/d = (dx - cy)/(dy) >= 1/(dy) Por outro lado, c/d - a/b = (bc - ad)/(bd) = 1/(bd) Assim: 1/(by) = (bx - ay)/(by) = x/y - a/b >= 1/(dy) + 1/(bd) = = (b + y)/(bdy) > N/(bdy) >= 1/(by) ==> contradicao ==> x/y = c/d Um abraco, Claudio. on 31.03.03 23:16, Helder Suzuki at [EMAIL PROTECTED] wrote: > Se temos todas frações reduzidas entre 0/1 e 1/1 > (inclusive) com denominadores <= N e ordenadas, qual a > K-ésima fração em função de N e K? > > por exemplo > se N = 3 > temos: > (0, 1/3, 1/2, 2/3, 1) > A1 = 0, A2 = 1/3, ..., A5 = 1 > > Abraços, > Helder Toshiro Suzuki > > _______________________________________________________________________ > Yahoo! GeoCities > Tudo para criar o seu site: ferramentas fáceis de usar, espaço de sobra e > acessórios. > http://br.geocities.yahoo.com/ > ========================================================================= > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html > O administrador desta lista é <[EMAIL PROTECTED]> > ========================================================================= > ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> =========================================================================