2
$\begingroup$

Per the title, I'm seeking the definition of a function $f(n, m)$ which evaluates to the number of lines made from exactly $n$ points which can be placed on a two-dimensional discrete, square grid of size $m \times m$.

My primary interest is the case where $n = 3$, as this is the answer I'm really after. I would've raised this question alone, however since I see that $n = 2$ has been answered already, I figured I might as well just generalize the question in hopes that there's some nice, elegant solution out there.

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
2
$\begingroup$

It seems that this has been answered here by S. Mustonen: PointsInGrid.pdf

There $f(n,m)$ is denoted by $L_n(m)$ and a formula would be $$L_n(m)=\frac{1}{2}[f(m,n+1)-2f(m,n)+f(m,n-1)]$$ for $$f(m,k)=\sum_{\substack{-m<kx<m\\-m<ky<m\\(x,y)=1}}(m-|kx|)(m-|ky|)$$

Improve this answer
$\endgroup$
3
  • $\begingroup$ Apologies, but I haven't encountered that form of sigma expression. Can you please give a quick example as to how it should be expanded? $\endgroup$ Commented May 31, 2016 at 9:39
  • $\begingroup$ I'm not quite sure what you mean: e.g. $L_2(2)=1/2(4-(2\cdot4)+(1+2+1+2+4+2+1+2+1))=6$ $\endgroup$ Commented May 31, 2016 at 10:02
  • $\begingroup$ Thanks, that's perfect. I managed to work backward from your expansion to figure it out well enough to code it up in Python. I was a bit thrown by the bounds of the indexes being defined below the sigma rather than above it. $\endgroup$ Commented May 31, 2016 at 10:28

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.