About Farey Sequences

The number of terms of Farey sequence $F_n$ is given by ( see Eqn. (10) ):

$N(n) = 1 + \sum_{k=1}^n \phi(k)$

where $\phi(\cdot)$ is the Euler's totient function .

It can be found that $N(40) = 491$ and $N(41) = 531$ , therefore the answer is $\boxed{40}$ .

---

Proof for $N(n)$ :

Consider $F_n$ for any $n$ ,

$\begin{aligned} F_n = \left \{\frac 01, \underbrace{\frac 11}_{\phi(1) \text{ terms}}, \underbrace{\frac 12}_{\phi(2) \text{ terms}}, \underbrace{\frac 13, \frac 23}_{\phi(3) \text{ terms}}, \underbrace{\frac 14, \frac 34}_{\phi(4) \text{ terms}}, ... \color{#3D99F6}{\underbrace{\frac {a_{n1}}n, \frac {a_{n2}}n, \frac {a_{n3}}n, ... \frac {a_{n \phi(n)}}n}_{\phi(n) \text{ terms}}} \right \} \end{aligned}$

We note that other than $\frac 01$ in the Farey sequence, all rational numbers with integer denominator $k$ must have coprime nominators $a_{kj}$ , therefore the number of rational numbers or terms with $k$ as denominator is Euler's totient function $\phi(k)$ . And we have:

$\begin{aligned} N(n) & = \sum_{k=1}^n \frac {a_{kj}}{k} = \color{#3D99F6}{1} + \sum_{k=1}^n \phi(k) \quad \blacksquare & \small \color{#3D99F6}{1 \text{ is for }\frac 01} \end{aligned}$