# How many irreducible fractions between 0 and 1 have denominator less than $n$?

Or, in an $n\times n$ grid of dots, how many distinct lines pass through at least two of the dots, one of which is the lower left dot? Is there a good way to do this?

Thanks.

-
–  Dylan Moreland Aug 21 '11 at 3:38

The list of such rational numbers is the Farey sequence of order $n$. The number of its elements is $$1+\sum_{m=1}^n \varphi(m)\sim \frac{3n^2}{\pi^2}$$ There are a lot of books that write about these sequences, and some very good references are given in the link above.
The lines described in the text can be split as the ones with slope $>1$ and $<1$, each of these is in bijection with a Farey sequence (removing the fraction $\frac{1}{1}$). –  Gjergji Zaimi Aug 21 '11 at 4:00