How can we count lines in an n-x-n rectangular array? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T13:11:02Z http://mathoverflow.net/feeds/question/2806 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/2806/how-can-we-count-lines-in-an-n-x-n-rectangular-array How can we count lines in an n-x-n rectangular array? pat ballew 2009-10-27T12:54:08Z 2010-04-21T12:22:18Z <p>Is there a formula for the number of lines that contain exactly two points through an <code>n x n</code> rectangular array of points?</p> http://mathoverflow.net/questions/2806/how-can-we-count-lines-in-an-n-x-n-rectangular-array/2807#2807 Answer by Anna Varvak for How can we count lines in an n-x-n rectangular array? Anna Varvak 2009-10-27T13:10:39Z 2009-10-27T13:34:18Z <p>Maybe it would be easier to count the number of lines in nxn which pass through more than two points.</p> <p>That's equivalent to asking how many 2ix2j rectangles there are in nxn, where i and j are relatively prime, except that it would overcount the lines that pass through 3 or more points. </p> <p>Let R_k = the number of ki x kj rectangles in nxn, where i and j are relatively prime. </p> <p>The number of lines passing through at least three points in nxn is R_2 - R_3.</p> http://mathoverflow.net/questions/2806/how-can-we-count-lines-in-an-n-x-n-rectangular-array/2835#2835 Answer by David Eppstein for How can we count lines in an n-x-n rectangular array? David Eppstein 2009-10-27T16:11:22Z 2009-10-27T16:36:24Z <p><b>(Updated in response to comments below:)</b></p> <p>I wrote a short Python program to count lines in small grids, which gave me enough data to search OEIS and find the answer at <a href="http://www.research.att.com/~njas/sequences/A018809" rel="nofollow">A018809</a>.</p> <p>Here is the code; the only real trick is to do everything in projective coordinates rather than staying in the Cartesian world.</p> <pre># Count lines through exactly two points in an n*n grid of points # dictionary mapping lines to the number of times they occur lines = {} def meet((a,b,c),(d,e,f)): """Line through two points or point on two lines.""" return ((b*f-c*e,c*d-a*f,a*e-b*d)) def same(l1,l2): """Do these two triples represent the same line?""" return meet(l1,l2)==(0,0,0) def add(l1): """Update the number of times line l1 has been generated.""" if l1 == (0,0,0): return for l2 in lines: if same(l1,l2): lines[l2] += 1 return lines[l1] = 1 for n in range(1,8): lines = {} for a in range(n): for b in range(n): for c in range(n): for d in range(n): add(meet((a,b,1),(c,d,1))) goodlines = 0 for line,count in lines.items(): if count == 2: goodlines += 1 print goodlines </pre> http://mathoverflow.net/questions/2806/how-can-we-count-lines-in-an-n-x-n-rectangular-array/22047#22047 Answer by Douglas S. Stones for How can we count lines in an n-x-n rectangular array? Douglas S. Stones 2010-04-21T12:16:35Z 2010-04-21T12:22:18Z <p>For $n \geq 3$ the gradient of these lines must be non-zero and finite. So it should be possible to give an answer expressed as a sum over all gradients which are reduced fractions $q/p$ with $-n \leq q \leq n$, $\,q \neq 0$ and $1 \leq p \leq n$.</p> <p>For a given gradient $q/p$ you could count the number points $(x,y) \in \{1,2,\ldots,n\}^2$ that satisfy:</p> <ul> <li>$1 \leq x+q \leq n$,</li> <li>$y+p \leq n$,</li> <li>$x-q \geq n+1$ or $x-q \leq 0$ or $y-q \leq 0$,</li> <li>$x+2q \geq n+1$ or $x+2q \leq 0$ or $y+2p \geq n+1$.</li> </ul> <p>The first two dot-points ensure that there is a second point $(x+q,y+p)$ on the line. The second two dot-points ensure that there is not too many points on the line -- that is, it ensures $(x+2q,y+2p)$ and $(x-q,y-p)$ are both not in $\{1,2,\ldots,n\}^2$.</p> <p>To give it as a formula, the number of lines that contain exactly two points in $\{1,2,\ldots,n\}^2$ is $\sum_{-n \leq q \leq n} \sum_{1 \leq p \leq n} \chi(q,p) |B_{q,p}|$ for $n \geq 3$, where $\chi(q,p)=1$ if $\gcd(q,p)=1$, and $\chi(q,p)=0$ otherwise, and $B_{q,p}$ is the subset of $\{1,2,\ldots,n\}^2$ for which the above four dot-points are satisfied.</p> <p>This should have $O(n^4)$ time complexity (which is not great, but it's better than most formulae I typically deal with).</p>