Detailed mathematical approach

Problem Summary

For each integer radius \(1 \le r \le 50\), consider the lattice points on the sphere \(x^2+y^2+z^2=r^2\). Among all non-degenerate triples of such points, let \(A(r)\) be the minimum spherical triangle area. The task is to compute

$\sum_{r=1}^{50} A(r).$

Mathematical Approach

Fix a radius \(r\). Every admissible vertex lies in

$\mathcal P_r=\{(x,y,z)\in\mathbb Z^3:x^2+y^2+z^2=r^2\}.$

The solution has three parts: generate \(\mathcal P_r\), evaluate the spherical area of each triple, and keep the minimum positive area.

1) Enumerating Lattice Points on the Sphere

The code loops over \(x,y\in[-r,r]\), computes

$z^2=r^2-x^2-y^2,$

and keeps the pair \((x,y)\) only when \(z^2\) is a non-negative perfect square. Then both \(z\) and \(-z\) are inserted when \(z\neq 0\). This generates exactly the integer points on the sphere.

For \(r\le 50\), the resulting set is small enough that a direct triple search is still practical.

2) Area from a Solid-Angle Formula

Take three lattice points \(a,b,c\in\mathcal P_r\). After normalization,

$u=\frac{a}{r},\qquad v=\frac{b}{r},\qquad w=\frac{c}{r},$

lie on the unit sphere. The spherical triangle area on the sphere of radius \(r\) is \(r^2\Omega\), where \(\Omega\) is the solid angle seen from the origin.

For unit vectors, a standard identity is

$\Omega=2\operatorname{atan2}\!\left(|u\cdot(v\times w)|,\ 1+u\cdot v+u\cdot w+v\cdot w\right).$

Scaling back to the radius-\(r\) vectors gives

$\Delta=|\det(a,b,c)|=r^3|u\cdot(v\times w)|,$

$D=r^3+r(a\cdot b+a\cdot c+b\cdot c)=r^3(1+u\cdot v+u\cdot w+v\cdot w).$

Therefore the exact formula implemented in the code is

$\Omega=2\operatorname{atan2}(\Delta,D),\qquad \operatorname{Area}=r^2\Omega.$

When \(D>0\), this is the same as \(2\arctan(\Delta/D)\), but the `atan2` form is numerically safer because it keeps numerator and denominator separate.

3) Why the Determinant Appears

The quantity \(|\det(a,b,c)|\) is the volume of the parallelepiped spanned by the three radius vectors. It is zero exactly when the vectors are coplanar with the origin, which means the spherical triangle is degenerate. So the code simply skips all triples with

$\Delta=0.$

4) Why Minimizing Area Reduces to Minimizing \(\Delta/D\)

For the candidates kept by the code we have \(\Delta>0\) and \(D>0\). On that domain, \(x\mapsto 2\arctan x\) is strictly increasing, so minimizing the area is equivalent to minimizing

$\frac{\Delta}{D}.$

This matters algorithmically: instead of computing floating-point areas for every triple, the program compares two candidates \(\Delta_1/D_1\) and \(\Delta_2/D_2\) using exact cross multiplication,

$\Delta_1D_2\lt \Delta_2D_1.$

The C++ version uses `__int128`, the Java version uses `BigInteger`, and Python relies on arbitrary-precision integers.

The condition \(D\le 0\) can also be discarded safely. Such triples satisfy \(\Omega\ge\pi\), hence their area is at least \(\pi r^2\). But the axis points \((r,0,0)\), \((0,r,0)\), \((0,0,r)\) are always present and give area \(\pi r^2/2\), so a minimum can never come from \(D\le 0\).

5) Worked Example: \(r=1\)

For \(r=1\), the lattice points are the six axis points \(\pm(1,0,0)\), \(\pm(0,1,0)\), \(\pm(0,0,1)\). Choose

$a=(1,0,0),\qquad b=(0,1,0),\qquad c=(0,0,1).$

Then

$\Delta=|\det(a,b,c)|=1,$

and every pairwise dot product is \(0\), so \(D=1\). Therefore

$\Omega=2\operatorname{atan2}(1,1)=\frac{\pi}{2},\qquad A(1)=1^2\cdot\frac{\pi}{2}=\frac{\pi}{2}.$

This is exactly the spherical octant triangle with three right angles, and it is a clean sanity check for the formula.

How the Code Works

For each radius \(r\), the implementation first builds the list of lattice points on the sphere. It then precomputes all pairwise dot products in an \(n_r\times n_r\) table, where \(n_r=|\mathcal P_r|\). This makes the denominator

$D=r^3+r(a\cdot b+a\cdot c+b\cdot c)$

available in \(O(1)\) time for each triple.

Next it scans all \(i<j<k\), skips degenerate triples, ignores \(D\le 0\), and keeps the best fraction \(\Delta/D\) using exact integer comparison. Only after the best triple is known does it evaluate one final `atan2` and multiply by \(r^2\). The C++ code also checks the published checkpoint \(A(14)\approx 3.294040\) before summing all radii.

Complexity Analysis

Let \(n_r=|\mathcal P_r|\). Point generation takes \(O(r^2)\) trial pairs \((x,y)\), dot-product precomputation takes \(O(n_r^2)\) time and memory, and the dominant triple scan takes \(O(n_r^3)\) time.

Because the problem stops at \(r=50\), every \(n_r\) stays small enough that this brute-force geometric search is completely feasible. The exact-integer comparison also keeps the result stable across all three language implementations.

Further Reading

1. Problem page: https://projecteuler.net/problem=332
2. Solid angle: https://en.wikipedia.org/wiki/Solid_angle
3. Spherical triangle and spherical excess: https://en.wikipedia.org/wiki/Spherical_triangle
4. Scalar triple product: https://en.wikipedia.org/wiki/Triple_product