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
    Depends. The OP asked two questions, one in the title and a related one in the text.2011-08-21
  • 0
    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}$).2011-08-21
  • 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