Farey Sequence

The Farey sequence of order $n$, denoted by $F_n$, is the sequence of the irreducible fractions in the interval from 0 to 1, arranged in the ascending order of magnitude. These fractions are in the form $\frac{a}{b}$ where $\gcd(a,b)=1$ and $0 \leqslant a \leqslant b \leqslant n$.

Here are some examples of Farey sequence: \[ \begin{array}{lll} F_1 & = & \left\{\frac{0}{1}, \frac{1}{1}\right\} \\ F_2 & = & \left\{\frac{0}{1}, \frac{1}{2}, \frac{1}{1}\right\} \\ F_3 & = & \left\{\frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1}\right\} \\ F_4 & = & \left\{\frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1}\right\} \end{array} \] The length of the sequence of order $n$, $|F_n|$, is the number of fractions in $F_n$. From the examples above we have $|F_1|=2$, $|F_2|=3$, $|F_3|=5$, and $|F_4|=7$. Generally, the total number of fractions in $F_n$ is calculated from the formula \[ |F_n| = 1 + \sum_{k=1}^n \phi(k) \] where $\phi$ is the Euler totient functions.

This application calculates the Farey sequence $F_n$ and the number of fractions in $F_n$ if $n$ is less than or equal 50. If $n$ is greater than 50 up to $10^{10}$, it calculates only the total number of fractions.

Farey Sequence Calculator