## Return to Answer

2 fixed typo

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-q)$ (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). 1 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-q)$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).