Suite de Farey

[youkef-sne]

Bonjour: J'ai un problème avec lema fameuse suite de Farey:
La suite de Farey d'ordre n, noté F(n) est la suite finie de fraction irréductibles comprises entre 0 et 1 dont le dénominateur est infèrieur ou égal a n. Les fractions sont rangées dans l'ordre croissant.
Exemple pour F(4):
F(4)=( 0/1 , 1/4 , 1/3 , 1/2 , 2/3 , 3/4 , 4/4 )
Puis il donne l'algorithme suivant:
:Input "N=",N
:0 -> A
:1 -> B
:1 -> C
:N -> D
:Disp "A/B=",A/B
:While C:partEnt((N+B)/D) -> K
:K*C-A -> E
:K*D-B -> F
:C -> A
:D -> B
:E -> C
:F -> D
:Disp "A/B=", A/B
:End
Puis on me dit: Si une fraction a/b est affichée a la fin de la boucle, comment obtenir la fraction suivante avec les meme variables de la même boucle ? Et celle d'après ?
Et a quoi sert la variable k ?

Pouvez vous m'éclaircir svp ?

[Ben314]

Salut,
Toute l'astuce réside dans le fait que, si et sont deux fraction (sous forme irréductible) successives d'une suite de la suite de Farey d'ordre alors .

Donc pour trouver le "suivant" de , il faut chercher et tels que .
Si tu as fait un peu d'arithmétique, tu sait qu'un tel couple existe dans du fait que et sont premiers entre eux.

Bon, après, je sais pas trop quelle est ta question :
1) La preuve du (joli) théorème énoncé au début de ce post.
2) La méthode pour calculer et connaissant et (ainsi que les deux éléments précédent de la suite) ?

[youkef-sne]

On demande quelle est la fraction suivante avec les variables a et b de laeme boucle ? Ils ne me demandent pas de trouver b et d tels que ad-bc=-1.

[Ben314]

PREUVE DU THEOREME : (par récurrence)

Pour , la suite est et on a bien

Supposons qu'on ait deux termes successifs de la suite .
On en déduit que ce qui est contraire à l'hypothèse.
3.2) Si on a .
On en déduit que ce qui est contraire à l'hypothèse.

[Ben314]

On demande quelle est la fraction suivante avec les variables a et b de laeme boucle ? Ils ne me demandent pas de trouver b et d tels que ad-bc=-1.

Ben... si, vu que c'est ça qui te permet de trouver le suivant...

Si tu as les trois fractions successives
De même,
Donc et et, on veut donc et on prend le plus grand possible pour que soit le plus petit possible.
On prend donc

[youkef-sne]

Ben... si, vu que c'est ça qui te permet de trouver le suivant...

Si tu as les trois fractions successives
De même,
Donc et et, on veut donc et on prend le plus grand possible pour que soit le plus petit possible.
On prend donc

Soit a/b une fraction de la suite de farey d'ordre n. La question c'est:
En utilisamt les variables a et b de la fraction a/b, quelle est la fraction suivantes ?
Ils ne demandent avec tros fractions successives

[Ben314]

Tu sais lire ?

[youkef-sne]

Euh... Je sais pas ca fait deux ans que j'ai pas eu cours de français en revanche je sais que c'est avec les memes variables a et b de la fraction a/b que l'on doit déterminer la fraction suivante d'une suite de Farey d'ordre n.

[Ben314]

Y'a écrit quoi là :

comment obtenir la fraction suivante avec les meme variables de la même boucle ?

et il me smble pas que A et B soient les seules variables de la boucle.

Et là, y'a écrit quoi :

...Donc et ...
On prend donc

Aprés, effectivement, on peut trouver la fraction suivante QUE avec A et B, mais il faut utiliser l'algo. d'Euclide pour déterminer u et v tels que au+bv=1 ce qui est pas mal plus compliqué que ce que fait ton programme.
Et en plus... c'est pas ça qu'on te demande...

[youkef-sne]

Y'a écrit quoi là :et il me smble pas que A et B soient les seules variables de la boucle.

Et là, y'a écrit quoi :

Aprés, effectivement, on peut trouver la fraction suivante QUE avec A et B, mais il faut utiliser l'algo. d'Euclide pour déterminer u et v tels que au+bv=1 ce qui est pas mal plus compliqué que ce que fait ton programme.
Et en plus... c'est pas ça qu'on te demande...

Et c'est quoi l'algo d'Euclide ?

[youkef-sne]

Wouah j'ai compris des fois je suis c** mais bon ! Merci !
Mais l variable k elle sert a quoi dans l'algorithme ?

[youkef-sne]

Donc si j'ai compris: k c'est la partie entière de (n-b)/d .
D'accord mais dans l'algorithme. elle sert a quoi la variable k ?

[Ben314]

P'tête ben à calculer la fraction suivante...

...Donc et

[Ben314]

Et c'est quoi l'algo d'Euclide ?

C'est un algo. pour trouver deux entiers u et v tels que au+bv=1 en partant de deux entiers a et b connus et premiers entre eux.

[youkef-sne]

Merci de ton aide Ben314 :-) :++: