Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
Farey sequences? –  Dylan Moreland Aug 21 '11 at 3:38
add comment

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.