Successió de Farey P62377

La successió de Farey d’ordre n és la seqüència ordenada de totes les fraccions irreductibles p/q tals que 0 ≤ p/q ≤ 1 i 1 ≤ q ≤ n. A l’exemple d’entrada podeu trobar les successions de Farey per a diversos valors d’n.

Hi ha un parell de propietats matemàtiques que permeten obtenir fàcilment la successió de Farey d’ordre n:

• Els dos primers termes són 0/1 i 1/n.
• Donats dos termes consecutius a/b i c/d, el terme següent és (x · c − a)/(x · d − b), on x = ⌊ (n + b)/d ⌋.

Feu un programa que escrigui la successió de Farey per a diversos valors d’n.

Entrada

L’entrada consisteix en diverses n, totes entre 1 i 100.

Sortida

Per a cada n, escriviu la successió de Farey d’ordre n.

Observació

No podeu usar vectors, matrius o similars.