Total number of lines in a 2D grid I have a 2D grid of $M \times N$ points. I need to find the total number of lines (not line segments) passing through these points including the diagonals. For example:


*

*$M=2,N=2$: Number of lines $= 6$ (2 horizontal, 2 vertical, 2 diagonals) 

*$M=2,N=3$: Number of lines $= 11$ (2 horizontal, 3 vertical, 6 diagonals) 

*$M=3,N=3$: Number of lines $= 20$ (3 horizontal, 3 vertical, 14 diagonals) 

*$M=2,N=4$: Number of lines $= 18$ (2 horizontal, 4 vertical, 12 diagonals) 

*$M=3,N=4$: Number of lines $= 35$ (3 horizontal, 4 vertical, 28 diagonals)
Can someone help me in finding a general formula to find this?
 A: The horizontal and vertical lines are straightforward.  You get $M+N$ of those.
Let's take the lower left of the array at the origin so that the top row of points is at $y = M-1$ and the right column is at $x=N-1$.
Let's consider those diagonal lines that have positive slope, with one of the points being the origin.
We get a distinct diagonal for each pair $(x,y)$ for which $x$ and $y$ are relatively prime.  (The line through $(0,0)$ and $(1,2)$ coincides with the one through $(0,0)$ and $(2,4)$.)
For counting the multiplicity, let's consider counting the lines with slope $2/3$ in a $9 \times 11$ grid.
If we start at the origin, this line goes through $(3,2)$.  We can move along the $x$ axis until $(7,0)$, and after that we run out of points.  We can go up a row, start at $(0,1)$ and go over again to $(7,1)$.
But if we go up to the next row, we can only go over to $(2,2)$ before we start running into points that we've drawn lines through.
However, we can continue to go up the left side.  We only can go out to $x=2$ for the reason mentioned above.  We can continue up to $(2,7)$, and that's the last new line for this slope.
So the formula for the number of lines with a rise of $m$ and a run of $n$ in an $M \times N$ grid is
$$L(M,N,m,n) = (m+1)(N-n) + (n+1)(M-m) - (m+1)(n+1) - 2.$$
Then, the total number of all lines (vertical, horizontal, positive slope, negative slope) is
$$T(M,N) = M + N + 2 \sum_{n=1}^{N-1} \sum_{m=1}^{M-1} L(M,N,m,n) C(m,n),$$
where $C(m,n) = 1$ if $m,n$ are coprime, and $0$ if they're not.
