Detailed mathematical approach

Problem Summary

For each integer circumradius \(r\), let \(T(r)\) be the number of triangles with integer side lengths and circumradius exactly \(r\). The program computes

$S(N)=\sum_{r=1}^{N} r\,T(r),\qquad N=10^7.$

A brute-force search over all triples \((a,b,c)\) up to \(2r\) would be far too slow, so the implementation first characterizes which side lengths can occur for a fixed radius and then checks only those candidates exactly.

Mathematical Approach

Step 1: Convert the circumradius condition into an exact integer identity

For a triangle with sides \(a,b,c\) and area \(\Delta\), Heron's formula gives

$16\Delta^2=(a+b+c)(a+b-c)(a-b+c)(-a+b+c).$

The circumradius also satisfies

$R=\frac{abc}{4\Delta}.$

Squaring and eliminating \(\Delta\) yields

$a^2b^2c^2=R^2(a+b+c)(a+b-c)(a-b+c)(-a+b+c).$

This is exactly the predicate used in the solver. It avoids floating-point roundoff entirely: once \(a\), \(b\), \(c\), and \(r\) are integers, the question “is the circumradius equal to \(r\)?” becomes a pure integer comparison.

Step 2: Describe every possible side length for a fixed radius

If side \(a\) is opposite angle \(A\), then the extended law of sines gives

$a=2r\sin A.$

Because \(a\) and \(r\) are integers, \(\sin A=a/(2r)\) is rational. Rational points on the unit circle are parameterized by primitive Pythagorean data: for coprime integers \(m>n\ge 1\) with opposite parity,

$\left(\frac{m^2-n^2}{m^2+n^2},\frac{2mn}{m^2+n^2}\right)$

is a primitive rational point on \(x^2+y^2=1\). Therefore every rational sine in \((0,1)\) can be written as one of

$\sin A\in\left\{\frac{m^2-n^2}{m^2+n^2},\frac{2mn}{m^2+n^2}\right\}.$

If we write \(d=m^2+n^2\) and \(u\) for one of the two numerators, then

$a=2r\frac{u}{d}.$

So \(a\) is guaranteed to be integral whenever \(d\mid r\). The special value \(\sin A=1\) is not produced by finite \((m,n)\), so the code inserts the diameter case \(a=2r\) explicitly.

Step 3: Precompute useful denominators once, then use only divisors of \(r\)

The C++ solver builds a table indexed by \(d\le N\). For each primitive pair \((m,n)\) with \(d=m^2+n^2\le N\), it stores the admissible numerators

$u\in\{m^2-n^2,\ 2mn\}.$

For a fixed radius \(r\), only denominators dividing \(r\) can contribute integer sides. If \(r=kd\), then each stored numerator produces the candidate side

$a=2ku.$

This is why the implementation first factors \(r\) using a smallest-prime-factor sieve, enumerates all divisors of \(r\), and looks up only those divisor entries. The resulting candidate set is

$\mathcal{S}_r=\{2r\}\cup \left\{2\frac{r}{d}u : d\mid r,\ u\in U(d)\right\},$

where \(U(d)\) is the precomputed list of numerators attached to denominator \(d\). The list is sorted and deduplicated because distinct parameter pairs can lead to the same side length.

Step 4: Count valid triples from the candidate side set

After building \(\mathcal{S}_r\), the solver enumerates

$a\le b\le c,\qquad a,b,c\in \mathcal{S}_r.$

The sorted order gives an immediate pruning rule: as soon as \(a+b\le c\), the triangle inequality fails and the inner loop can stop for that pair \((a,b)\). For each remaining triple, the solver applies the exact identity from Step 1. Every triple that passes contributes \(1\) to \(T(r)\).

A simple example is \(r=5\). The primitive pair \((m,n)=(2,1)\) gives \(d=5\) and numerators \(3\) and \(4\). Because \(5\mid r\), the candidate sides include

$2\cdot \frac{5}{5}\cdot 3=6,\qquad 2\cdot \frac{5}{5}\cdot 4=8,\qquad 2r=10.$

So \((6,8,10)\) appears naturally, and the exact check confirms that its circumradius is indeed \(5\).

How the Code Works

The class Euler373Solver precomputes two structures: a smallest-prime-factor array for fast divisor generation, and a denominator-to-numerators table for rational-sine candidates. The method count_triangles_for_radius(r) builds \(\mathcal{S}_r\), loops over ordered triples, and calls circumradius_equals(a,b,c,r) for the exact test.

The C++ implementation uses a custom 192-bit accumulator U192 because the products in the circumradius identity are too large for ordinary 64-bit arithmetic. The outer sum over radii is embarrassingly parallel, so the solver distributes radii across worker threads with an atomic counter and combines per-thread partial sums. The Python and Java files are thin bridges that compile and run this same C++ solver, so all three language solutions share identical mathematics and validation.

Before solving the full problem, the program checks the optimized method against brute force for \(r\le 60\) and also verifies the checkpoints

$S(100)=4950,\qquad S(1200)=1653605.$

Complexity Analysis

Let \(N\) be the radius limit. Building the smallest-prime-factor table costs \(O(N\log\log N)\) time and \(O(N)\) memory. The denominator table iterates over primitive pairs with \(m^2+n^2\le N\), which is a one-time precomputation.

For one radius \(r\), divisor enumeration is proportional to the number of divisors of \(r\), and the dominant work is the triple scan over the deduplicated candidate set \(\mathcal{S}_r\). In the worst case this stage is \(O(|\mathcal{S}_r|^3)\), but in practice it is kept manageable because only divisors of \(r\) contribute candidates, duplicates are removed, and the triangle inequality stops many inner-loop iterations early. The final summation over radii is parallelized.

References

1. Problem page: https://projecteuler.net/problem=373
2. Circumradius formulas and the extended law of sines: Wikipedia — Circumscribed circle
3. Heron's formula: Wikipedia — Heron's formula
4. Primitive Pythagorean triples and rational points on the unit circle: Wikipedia — Pythagorean triple