5
$\begingroup$

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.

  • 3
    [Farey sequences](http://en.wikipedia.org/wiki/Farey_sequence)?2011-08-21

1 Answers 1

7

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.

  • 0
    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.2011-08-21