Re: [obm-l] K-ésimo número da sequência! (A reencarnação)

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

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 heldersuzuki@yahoo.com.br 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 é <nicolau@mat.puc-rio.br>
> =========================================================================
> 

=========================================================================
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 é <nicolau@mat.puc-rio.br>
=========================================================================