Detailed mathematical approach

Problem Summary

We search for triangles with integer vertices \(A,B,C\in\mathbb{Z}^2\) such that all three points lie on the same circle centered at the origin and the centroid is fixed by

$A+B+C=(5,0).$

For every such triangle whose perimeter does not exceed the given limit, we add its perimeter to the total. The solver prints the final sum rounded to four decimal places.

Mathematical Approach

1. Turn the centroid condition into a vector equation

Because the centroid is \((5/3,0)\), the vertex sum is the integer vector

$H=(5,0).$

If we choose one vertex \(C=(c_x,c_y)\), then the remaining two vertices satisfy

$A+B=H-C=(5-c_x,-c_y).$

The code calls this vector \(S\). Once \(C\) is fixed, the whole problem becomes: find integer pairs \(A,B\) with sum \(S\), equal distance from the origin, and correct perimeter.

2. Split the pair \(A,B\) into sum and difference

Write

$A=\frac{S+U}{2},\qquad B=\frac{S-U}{2},\qquad U:=A-B.$

Then \(A\) and \(B\) have equal radius if and only if

$|A|^2=|B|^2 \iff U\perp S.$

Moreover, if the common radius is \(R\), then

$|U|^2=4R^2-|S|^2,$

because

$4|A|^2=|S+U|^2=|S|^2+|U|^2,$

and the same expression holds for \(B\). This is the central identity used by the code.

3. Integer orthogonal vectors via a gcd basis

Since \(S=(s_x,s_y)\) is integral, every integer vector orthogonal to \(S\) lies on a one-dimensional lattice. Let

$g=\gcd(|s_x|,|s_y|),\qquad P=\left(-\frac{s_y}{g},\frac{s_x}{g}\right).$

Then \(P\) is the primitive integer normal vector to \(S\), and every integer orthogonal vector is

$U=tP,\qquad t\in\mathbb{Z}.$

Substituting this into the radius identity gives

$t^2=\frac{(4R^2-|S|^2)g^2}{|S|^2}.$

The solver checks exactly this quantity: it must be an integer square before \(A\) and \(B\) are even constructed.

4. Parity, degeneracy, and canonical uniqueness

Once \(U\) is known, the coordinates of \(A\) and \(B\) are obtained from \((S\pm U)/2\). Therefore each coordinate must have the correct parity; otherwise the pair is discarded immediately.

The code then rejects degenerate triangles by checking that the doubled area, computed by a cross product, is nonzero.

To avoid counting the same triangle multiple times, the code keeps only a canonical representative: the chosen vertex \(C\) must be lexicographically no larger than \(A\) and \(B\). This removes the six permutations of the same unlabeled triangle, while the fixed sign choice for the primitive normal vector removes the \(A\leftrightarrow B\) swap.

5. Why the search for \(C\) is bounded

The code does not scan all possible radii blindly. It first derives an upper bound on the circumradius from the perimeter cap.

Using

$AB^2=4R^2-|A+B|^2=4R^2-|H-C|^2,$

and the triangle inequality \(|H-C|\le |H|+|C|=5+R\), we get

$AB^2\ge 4R^2-(R+5)^2=3R^2-10R-25.$

The same lower bound applies symmetrically to the three sides, so

$P\ge 3\sqrt{3R^2-10R-25}.$

Solving this inequality for \(R\) gives the radius cutoff used in the program. After that, the solver only scans integer points \(C=(c_x,c_y)\) with \(|C|\le R_{\max}\), and because \(C\) is the lexicographically smallest vertex, its \(x\)-coordinate must satisfy \(c_x\le 1\). That is why the outer scan stops at \(x=1\).

6. Threading and numeric robustness

The implementation splits the \(c_x\)-range into chunks and distributes them across threads. Each thread keeps a local perimeter sum and triangle count, and the partial sums are merged at the end.

Geometric tests that need exactness use integer arithmetic and the integer square root helper. The final perimeter is computed with long double, then rounded to four decimals. The checkpoints in the code verify both a sample perimeter value and that the multi-threaded and single-threaded runs agree.

The checkpoints are concrete: the code requires round4(solve(50, 1)) = 291.0089, and it also checks that solve(300, 1) matches a multi-threaded run. One checkpoint validates the geometric pipeline numerically, and the other validates that the thread split does not change the result.

7. Worked structural example

Take the valid triangle

$C=(-4,-3),\qquad A=(4,3),\qquad B=(5,0).$

All three vertices satisfy

$|A|^2=|B|^2=|C|^2=25,$

and also

$A+B+C=(4+5-4,\ 3+0-3)=(5,0).$

For this choice of \(C\), we get

$S=H-C=(9,3),\qquad g=\gcd(9,3)=3,\qquad P=(-1,3).$

The radius identity gives

$t^2=\frac{(4\cdot 25-90)\cdot 3^2}{90}=1,$

so \(t=1\) and therefore

$U=tP=(-1,3).$

Reconstructing the pair yields

$A=\frac{S+U}{2}=(4,3),\qquad B=\frac{S-U}{2}=(5,0).$

This is exactly what the code does for every admissible \(C\): derive \(S\), test whether the induced \(t^2\) is a perfect square, then rebuild \(A\) and \(B\) algebraically instead of enumerating all vertex triples.

How the Code Works

The program accepts --perimeter, --threads, and --skip-checkpoints. The function solve first converts the perimeter limit into a radius bound \(R_{\max}\). It then scans integer points \(C=(c_x,c_y)\) inside that circle. For each \(C\), it forms

$S=(5-c_x,-c_y),\qquad r^2=|C|^2.$

After that it computes the primitive orthogonal vector \(P\), checks that the derived \(t^2\) is a perfect square, verifies parity, reconstructs \(A\) and \(B\), rejects degenerate or non-canonical triangles, and finally filters by the exact perimeter bound.

The helper isqrt_i64 is used both for radius estimates and square tests. The helper lex_leq implements the canonical ordering. The checkpoint routine compares the single-threaded and multi-threaded results and also checks the stored sample sum for perimeter \(50\).

Complexity Analysis

The dominant work is the scan over candidate vertices \(C\) in the bounded disk. For each candidate, the solver performs only constant-time arithmetic, gcd, square-root, and geometry checks. Because the scan is restricted to \(c_x\le 1\) and \(|C|\le R_{\max}\), the search space is much smaller than all triples of vertices.

Time grows roughly quadratically with the radius bound, and the multi-threaded split reduces wall-clock time without changing the mathematics. Memory usage stays small because the solver keeps only a few counters and partial sums.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=264
2. Primitive lattice vectors and Gaussian integers: Wikipedia - Gaussian integer
3. Sum/difference decomposition: Wikipedia - Parallelogram law
4. Integer square root and exact arithmetic: Wikipedia - Integer square root