Exercices (pc1)

La suite de Farey d’ordre n est la suite croissante F_{n} des nombres rationnels h/k compris entre 0 et 1 tels que k ≤ n. Ainsi

F_{5} = (\frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1})

On admettra que si h/k et h′/k′ sont consécutifs, alors :

h′k − hk′ = 1

et que si h/k, h′′/k′′ et h′/k′ sont consécutifs, le terme médian est

\frac{h′′}{k′′} = \frac{h + h′}{k + k′}

1. Ecrire une procedure qui calcule la suite F_{n}

2. Montrer que h/k et h′′/k′′ sont consécutifs dans F_{n}, le troisième terme est donné par la formule :

h′ = fh′′ − h, k′ = fk′′ − k

avec f = ⌊(k + n)/k′′⌋.

En déduire une deuxième procedure qui calcule séquentiellement les termes de la suite F_{n}.