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

Question

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.

Answer 1

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.