The Farey Sequence

Order of Fractions

The Farey sequence of order $n$ is the sequence of completely reduced fractions between 0 and 1 which have denominators less than or equal to $n$. Example order 3: $0/1, 1/3, 1/2, 2/3, 1/1$.

The Assignment

Your function receives a parameter n.

1. Initialize $(a, b) = (0, 1)$ and $(c, d) = (1, n)$.
2. Use a while loop to generate the next pair using the formula: $k = lfloor (n + b) / d floor$ $next_a = k imes c - a$ $next_b = k imes d - b$
3. Print each fraction as "a/b" on a new line.
4. Stop when $a/b$ reaches $1/1$.