Detailed mathematical approach

Problem Summary

Let \(r\) be divisible by 4 and set \(a=r/4\). The fixed vertices are \(O=(0,0)\) and \(C=(a,a)\). The third vertex \(B=(x,y)\) ranges over all lattice points in the taxicab diamond

$|x|+|y|\le r.$

The task is to count how many non-degenerate triangles \(OBC\) are obtuse. The geometric difficulty is that the allowed points form an \(L_1\)-ball rather than a Euclidean circle, while the obtuse-angle test itself is Euclidean. The implementations resolve this by splitting the count according to which vertex is obtuse and then converting the only nonlinear case into a lattice-point count inside a circle with a parity restriction.

Mathematical Approach

Separating the three obtuse-angle cases

A triangle is obtuse exactly when one of its angles has negative dot product. With \(B=(x,y)\) and \(C=(a,a)\), the three angle tests are

$\overrightarrow{OB}\cdot\overrightarrow{OC}=a(x+y),$

$\overrightarrow{CO}\cdot\overrightarrow{CB}=2a^2-a(x+y),$

$\overrightarrow{BO}\cdot\overrightarrow{BC}=x^2+y^2-a(x+y).$

Therefore the triangle is obtuse at

$O \iff x+y \lt 0,$

$C \iff x+y \gt 2a=\frac r2,$

$B \iff x^2+y^2-a(x+y) \lt 0.$

These three regions can be counted separately, because a non-degenerate triangle cannot have more than one obtuse angle. The only overlap that matters is the collinear line \(y=x\), which will be removed at the end.

Counting the region where the angle at \(O\) is obtuse

The diamond \( |x|+|y|\le r \) contains

$1+2r(r+1)=2r^2+2r+1$

lattice points in total. The boundary line between \(x+y \lt 0\) and \(x+y \gt 0\) is \(x+y=0\), whose lattice points are \((t,-t)\) with \(|t|\le r/2\), so it contributes exactly \(r+1\) points.

By symmetry of the diamond across the line \(x+y=0\), the strict half-plane \(x+y \lt 0\) contains half of the remaining points:

$N_O=\frac{(2r^2+2r+1)-(r+1)}{2}=r^2+\frac r2.$

This is the first closed-form term used by the implementations.

Counting the region where the angle at \(C\) is obtuse

For the inequality \(x+y \gt r/2\), it is convenient to switch to diagonal coordinates

$p=x+y,\qquad q=x-y.$

Because \(x=(p+q)/2\) and \(y=(p-q)/2\), the lattice condition becomes \(p\equiv q\pmod 2\), and the diamond condition becomes

$|p|\le r,\qquad |q|\le r.$

Now fix a diagonal level \(p=s\) with \(r/2 \lt s\le r\). The allowed points on that level are exactly the integers \(q\in[-r,r]\) with the same parity as \(s\). When \(s\) is even there are \(r+1\) such values of \(q\); when \(s\) is odd there are \(r\).

Since \(r\) is divisible by 4, the levels \(s=r/2+1,r/2+2,\dots,r\) contain exactly \(r/4\) even values and \(r/4\) odd values. Hence

$N_C=\frac r4(r+1)+\frac r4 r=\frac{r(2r+1)}{4}.$

This is the second closed-form term.

Turning the angle at \(B\) into a circle count

The third condition is the only nonlinear one:

$x^2+y^2-a(x+y) \lt 0.$

Completing the square gives

$\left(x-\frac a2\right)^2+\left(y-\frac a2\right)^2 \lt \frac{a^2}{2},$

or, after multiplying by 4,

$ (2x-a)^2+(2y-a)^2 \lt 2a^2. $

So the points with an obtuse angle at \(B\) are exactly the lattice points strictly inside the circle whose diameter is \(OC\). The implementations use the scaled coordinates

$u=2x-a,\qquad v=2y-a,$

because then \(u\) and \(v\) are integers and both have the same parity as \(a\). Since the left-hand side is an integer, the strict inequality is equivalent to

$u^2+v^2\le 2a^2-1.$

Thus \(N_B\) is a lattice-circle count with a fixed parity pattern. The code scans admissible nonnegative \(u\)-values in steps of 2, keeps the largest same-parity \(v\) satisfying the circle inequality, and moves that \(v\)-pointer only downward. If the current maximum is \(v\), then the number of signed same-parity values from \(-v\) to \(v\) is \(v+1\), and the column contributes once when \(u=0\) and twice when \(u\ne 0\) because of the symmetry \(u\leftrightarrow -u\).

Worked example: \(r=8\)

Here \(a=2\). The three main pieces are

$N_O=8^2+\frac 82=68,\qquad N_C=\frac{8(17)}{4}=34.$

For the \(B\)-obtuse region, the inequality becomes

$x^2+y^2-2(x+y)\lt 0\iff (x-1)^2+(y-1)^2\lt 2.$

The integer points strictly inside that circle are

$ (1,0),\ (0,1),\ (1,1),\ (2,1),\ (1,2), $

so \(N_B=5\). One of them, namely \((1,1)\), lies on the line \(y=x\) and is degenerate. After the global correction discussed below, the total becomes

$68+34+5-7=100,$

which matches the small checkpoint used by the implementations.

Why the degenerate correction is \(r-1\)

All points \(B=(t,t)\) with \(-r/2\le t\le r/2\) are collinear with \(O\) and \(C\), so they do not form valid triangles. Two of these points, \(t=0\) and \(t=a\), are \(O\) and \(C\) themselves and were never counted, because the corresponding dot products are zero rather than negative.

Every other point on \(y=x\) was counted exactly once by the three cases above:

$t\lt 0 \Rightarrow \text{counted in }N_O,$

$0\lt t\lt a \Rightarrow \text{counted in }N_B,$

$t\gt a \Rightarrow \text{counted in }N_C.$

The number of such points is

$\frac r2+\left(\frac r4-1\right)+\frac r4=r-1.$

Therefore the final formula is

$N(r)=N_O+N_C+N_B-(r-1).$

How the Code Works

The C++, Python, and Java implementations first compute \(a=r/4\), then evaluate the two closed-form contributions \(N_O=r^2+r/2\) and \(N_C=r(2r+1)/4\) directly with integer arithmetic. No floating-point geometry is needed for those parts.

The only iterative part is \(N_B\). The implementation converts the problem to \(u^2+v^2\le 2a^2-1\) with \(u\equiv v\equiv a\pmod 2\). It finds the initial admissible \(v\) with an integer square root, iterates over admissible \(u\)-values in steps of 2, and shrinks \(v\) only when the current pair lies outside the circle. Because the maximum feasible \(v\) never increases as \(u\) increases, this is a monotone sweep rather than a two-dimensional search.

For each accepted \(u\), the implementation adds \(v+1\) same-parity values of \(v\) and doubles the contribution unless \(u=0\). After that it subtracts the universal degeneracy correction \(r-1\). The C++ implementation also includes small-radius checkpoint tests and can split the \(u\)-range across worker threads, while the Python and Java implementations perform the same mathematics serially.

Complexity Analysis

The two linear-half-plane counts and the final degeneracy correction are \(O(1)\). The circle phase examines only admissible \(u\)-values, so its outer loop has \(O(a)\) iterations, and the \(v\)-pointer moves downward at most \(O(a)\) times overall. Hence the total running time is \(O(a)=O(r)\), with \(a=r/4\).

The memory usage is \(O(1)\) for the serial implementations and still \(O(1)\) extra per worker in the threaded C++ variant. The key optimization is that the circle is never sampled point by point; instead, each admissible \(u\)-column is counted in one step after locating its topmost valid \(v\).

Footnotes and References

1. Project Euler problem page: Problem 210 - Obtuse Angled Triangles
2. Dot product and angle tests: Wikipedia - Dot product
3. The circle with diameter \(OC\) and the obtuse-angle criterion: Wikipedia - Thales's theorem
4. The diamond \( |x|+|y|\le r \) as a taxicab ball: Wikipedia - Taxicab geometry
5. Lattice-point counting in circles: Wikipedia - Gauss circle problem