# 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.

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.

• Depends. The OP asked two questions, one in the title and a related one in the text. – André Nicolas Aug 21 '11 at 3:54
• 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
• Thanks everyone! Now why didn't this appear in Google search... Currently searching "irreducible fractions with denominator less than" gives me this page on the second page of results already, while the Wikipedia page for Farey sequence, the first sentence of which is "In mathematics, the Farey sequence of order n is the sequence of completely reduced fractions between 0 and 1 which, when in lowest terms, have denominators less than or equal to n, arranged in order of increasing size", is not among the first 50 results. – JohnJamesSmith Aug 21 '11 at 4:01