Number of distinct angles that can be formed on a square grid

Given a set of grid points arranged in an $n$ by $n$ square (in 2 dimensions):

How many distinct proper (acute or obtuse) angles can be formed having a vertex on one grid point and line segments ending on two other grid points?

For example, on a $2 \times 2$ grid you can form only $2$ distinct angles, with cosines equal to $0$ (for example $\angle (0,0)(0,1)(1,1)$) and $\frac{1}{\sqrt{2}}$.

(I find it convenient to classify the angles by their cosines, because the law of cosines lets you easily get the cosine of each angle of a triangle on the grid.)

On a $3 \times 3$ grid, by adding that layer of 5 more points, you can form an additional $8$ distinct angles, with $$\cos \alpha \in \{ \frac{1}{\sqrt{5}},\frac{2}{\sqrt{5}},\frac{3}{5},-\frac{1}{\sqrt{2}}, \frac{3}{\sqrt{10}}, \frac{1}{\sqrt{10}}, \frac{4}{5}, - \frac{1}{\sqrt{5}} \} $$ Here I have arranged these values in an order that came from the following reasoning: To make a new angle, you must make a triangle with two vertices more that $n-1$ apart in either the horizontal or the vertical direction (or both. So I start with one point at the upper left grid point, slide a second point along the opposite edge, and work my way through all combinations of on point on each of two opposite edges. For each such combination, the third point can in principle be on any of the remaining grid points.

A very crude upper limit can be estimated by saying there are $\binom{n^2}{3}$ possible triangles, thus $3 \binom{n^2}{3}\approx \frac{n^6}{2}$ angles; but of course most of those angles will duplicate each other.

By considering the ordering described above, one eliminates a number of angles that are just translations, flips, or $90^\circ$ rotations of others already counted. Here, the naive upper limit for the added angles would be $3$ for the angles in a triangle, times $\binom{n+1}{2}$ for the ways to choose the two edge vertices, divided by $2$ to account for flips about the horizontal center of the square, times $(n^2-2)$ internal points. That gives a naive upper limit of about $\frac{3n^4}{4}$ points added when the square side increases from $n-1$ to $n$, thus a naive upper limit of $$ \Bbb{A}(n) \leq \frac{3n^5}{20} $$ But that is also much too large. Some triangles are duplicates because of:

• Much of the time, one or two of the angles in a new large triangle overlays an angle that can fit in a smaller grid.
• Any time the third vertex of the triangle lies below the first vertex, the whole triangle can be translated upward such that the first vertex lies on a corner.
• Symmetry that we have not yet discounted for (for example, some triangles are isosceles [although noe will be equilateral]).
• A side of a triangle passes through a grid point, allowing an angle to have been created on a smaller grid even though the triangle at hand is large. The counting of these cases involves the totient function.
• A triangle is similar to some other smaller triangle in some obvious way involving $45^\circ$ rotations.
• When a side that is neither horizontal nor vertical happens to have integer length due to Pythagorean relationships, angles involving that side are usually duplicated in other triangles with a horizontal or vertical side of that length.
• There are some numerical "coincidences" that cannot be anticipated by accounting for those other effects. This is fundamentally a number theory problem.

Although I originally suspected that the number of distinct angles grows like $n^4$, I have not been able to show this, nor get a handle on what the coefficient would be. I do know that for modest values of $n$, the growth appears to be much slower than this, perhaps as slow as $n^3$.

$\Bbb{A}(4)$ Appears to be $2 + 8 + 18 = 28$. I'm pretty sure that pattern breaks down by $\Bbb{A}(5)$.

Any progress or solution on this would be appreciated.

Added after a few days:

I have tightened the upper limit: Since any triangle touching the right and left sides can be translated and possibly flipped so that it has one vertex on the upper left corner and one on the right side, and since among those triangles the ones with the third vertex above the line joining the sides replicate triangles with the third vertex below that line, the upper limit, ignoring symmetries, coincidences, and so forth, is just $\frac{3n^2}{16}$ new angles for layer $n$. Thus $$ \Bbb{A}(n) \leq \frac{3n^4}{16} $$

I did an automated computation of $\Bbb{A}(n)$ for $n \leq 100$ and observe that $$ \Bbb{A}(n) \leq \frac{n^4}{8} $$ and that it appears to approach that limit.

The numbers in the sequence for $n = 2$ through $10$ are $$ \begin{array}{ll} 2 & 2 \\ 3 & 10 \\ 4 & 28 \\ 5 & 66 \\ 6 & 154 \\ 7 & 269 \\ 8 & 473 \\ 9 & 781 \\ 10 & 1156 \end{array} $$ I want to submit this as a new sequence in OEIS, but I won't until somebody else has confirmed my results by their own calculation, at least for ten more values of $n$. To be confident that this is a confirmation, I am not displaying the number of angles for all further values of $n$, but I will say that $\Bbb{A}(21) = 23640$, $\Bbb{A}(50) = 759308$, and $\Bbb{A}(100) = 12335703$,.

To increase the chances of somebody providing the verification I need,,

I am offering a bounty for even the values of $\Bbb{A}(n)$ from $10 < n < 21$.

Agreement in those ten numbers will tell me that my program was correct, and I will submit this to the Online Encyclopaedia of Integer Sequences.

Of course, any substantial theoretical work toward an actual understanding of the sequece would also earn the bounty!

Solution 1:

Below are the values I obtain. (I include all possible values of $\cos$ including $1$ and $-1$). Hence, to compare with yours subtract $2$ from $N$ except for the first one where you just subtract $1$. And add my name when you add to OEIS.

\begin{array} C n & N\\ 2 & 3\\ 3 & 12\\ 4 & 30\\ 5 & 68\\ 6 & 156\\ 7 & 271\\ 8 & 475\\ 9 & 783\\ 10 & 1158\\ 11 & 1691\\ 12 & 2539\\ 13 & 3232\\ 14 & 4637\\ 15 & 6014\\ 16 & 7641\\ 17 & 9757\\ 18 & 12878\\ 19 & 15297\\ 20 & 19535\\ 21 & 23642\\ 22 & 27937\\ 23 & 32994\\ \end{array}