How can we count lines in an n-x-n rectangular array? - MathOverflow

How can we count lines in an n-x-n rectangular array?

2009-10-27T12:54:08Z

Is there a formula for the number of lines that contain exactly two points through an n x n rectangular array of points?

Answer by Anna Varvak for How can we count lines in an n-x-n rectangular array?

2009-10-27T13:10:39Z

Maybe it would be easier to count the number of lines in nxn which pass through more than two points.

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.

Let R_k = the number of ki x kj rectangles in nxn, where i and j are relatively prime.

The number of lines passing through at least three points in nxn is R_2 - R_3.

Answer by David Eppstein for How can we count lines in an n-x-n rectangular array?

2009-10-27T16:11:22Z

(Updated in response to comments below:)

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

Here is the code; the only real trick is to do everything in projective coordinates rather than staying in the Cartesian world.

# 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

Answer by Douglas S. Stones for How can we count lines in an n-x-n rectangular array?

2010-04-21T12:16:35Z

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

For a given gradient $q/p$ you could count the number points $(x,y) \in \{1,2,\ldots,n\}^2$ that satisfy:

$1 \leq x+q \leq n$,
$y+p \leq n$,
$x-q \geq n+1$ or $x-q \leq 0$ or $y-q \leq 0$,
$x+2q \geq n+1$ or $x+2q \leq 0$ or $y+2p \geq n+1$.

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

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.

This should have $O(n^4)$ time complexity (which is not great, but it's better than most formulae I typically deal with).