How many distinct distances in an $n$ x $n$ lattice?

Question

I calculated the values to this question for $n = 2 - 14$ and got: $2, 5, 9, 14, 19, 26, 33, 41, 50, 60, 70, 82,$ and $92$. I can't figure out the pattern going on here, and this sequence aren't on OEIS. I suppose the problem could be generalized to the $n$ x $n$ x $n$ 3D lattice, the $n$x $n$x $n$x $n$ 4D and so on, but I couldn't even figure out the 2D case.

Answer 1

A simple formula probably doesn't exist, and here's why.

---

We can rephrase the problem to (equivalently) distinct squared distances, in which case $$d^2 = (x_1 - x_2)^2 + (y_1 - y_2)^2$$ where both $|x_1-x_2|$ and $|y_1 - y_2|$, not both $0$, range from $0$ to $n-1$. So $d^2$ is an integer between $1$ and $2(n-1)^2$, but not all integers can be expressed in this form, and there are two challenges to figuring out which ones they are:

• The sum of two squares theorem tells us which numbers between $1$ and $2(n-1)^2$ can be written in this way, but it's a characterization in terms of prime factorizations: not good news for finding exact formulas.
• Moreover, even if we write a squared distance as the sum of two squares, one of them may be larger than $n-1$, which further rules it out.

---

That's the bad news. The good news is that if you add $1$ to your sequence (to account for the value $0$, which is not a distance but fits into the pattern) we get A047800 on OEIS. This doesn't tell us anything we didn't know, but gives a conjectured asymptotic formula $$a_n \sim \frac{c n^2}{\sqrt{\log n}}, \qquad c \approx 0.79\dots$$ proposed by Landau and Erdős, and some citations.