Detailed mathematical approach

Problem Summary

The repository solutions work with the triangle family whose side lengths are

$\sqrt{b^2+1},\qquad \sqrt{c^2+1},\qquad \sqrt{b^2+c^2},$

where \(b\) and \(c\) are positive integers and the brute-force validator counts only unordered pairs \(b \le c\). If \(A\) denotes the area, the goal is

$S(L)=\sum A,$

summed over all triangles in this family whose area is an integer and satisfies \(A \le L\).

Mathematical Approach

Step 1: Reduce the Geometry to an Integer Square Test

Let

$x=\sqrt{b^2+1},\qquad y=\sqrt{c^2+1},\qquad z=\sqrt{b^2+c^2}.$

Applying Heron's identity in the form

$16A^2=2x^2y^2+2y^2z^2+2z^2x^2-x^4-y^4-z^4$

and substituting \(x^2=b^2+1\), \(y^2=c^2+1\), \(z^2=b^2+c^2\) gives

$16A^2=4\left(b^2c^2+b^2+c^2\right).$

Therefore

$A=\frac{1}{2}\sqrt{b^2c^2+b^2+c^2}.$

This is exactly the relation used by the C++ brute-force checkpoint. Writing

$m^2=b^2c^2+b^2+c^2,$

we have \(A=m/2\). So the area is integral precisely when \(m\) is an even integer square root of that expression.

Step 2: Parity Forces Even Parameters

Because \(A\) is an integer, \(m=2A\) is even, so \(m^2 \equiv 0 \pmod 4\). But a square is only \(0\) or \(1\) modulo \(4\). If either \(b\) or \(c\) were odd, then

$b^2c^2+b^2+c^2 \equiv 1 \text{ or } 3 \pmod 4,$

which is impossible. Hence every valid solution has even \(b\) and even \(c\). We may therefore write

$b=2p,\qquad c=2q,$

with integers \(p,q \ge 1\). Substituting into the area formula gives

$A^2=4p^2q^2+p^2+q^2.$

This is the equation actually encoded by the fast state generator.

Step 3: A Pell-Type Equation for Fixed \(p\)

For a fixed seed \(p\), move the \(q\)-term to the left:

$A^2-(4p^2+1)q^2=p^2.$

If we define

$D_p=4p^2+1,$

then every admissible state satisfies the Pell-type norm equation

$A^2-D_p q^2=p^2.$

The trivial solution is \(q=0\), \(A=p\). The fast solver starts from this trivial point and moves to the next positive one on the same Pell branch.

Step 4: Derive the Linear Recurrence Used in Code

The fundamental unit for \(x^2-D_p y^2=1\) used by the implementation is

$u_p=(8p^2+1)+4p\sqrt{D_p},$

because

$\left(8p^2+1\right)^2-D_p(4p)^2=1.$

Multiplying one solution \(A+q\sqrt{D_p}\) by \(u_p\) produces the next solution on the same branch:

$A'+q'\sqrt{D_p}=u_p\left(A+q\sqrt{D_p}\right).$

Comparing coefficients yields

$q'=(8p^2+1)q+4pA,$

$A'=4p(4p^2+1)q+(8p^2+1)A.$

This is exactly the transition implemented in all three solution files with

$a=8p^2+1,\qquad b=4p,\qquad c=4p(4p^2+1),$

$q'=a q+b A,\qquad A'=c q+a A.$

Step 5: First Nontrivial Area and the Seed Bound

Starting from the trivial state \((p,0,p)\), one recurrence step gives

$q_1=4p^2,\qquad A_1=(8p^2+1)p=8p^3+p.$

So the first actual triangle for seed \(p\) is

$b=2p,\qquad c=2q_1=8p^2,\qquad A=8p^3+p.$

This explains the helper function seed_first_area(p) and the binary search in max_seed(limit): once \(8p^3+p>L\), that seed cannot contribute any valid area \(\le L\).

For \(p=1\), the first solution is

$q_1=4,\qquad A_1=9,$

so \((b,c)=(2,8)\). The checkpoint in the C++ file confirms

$2^2\cdot 8^2+2^2+8^2=324=18^2,\qquad A=18/2=9.$

Step 6: Why the Solver Uses Three Branches

The equation

$A^2=4p^2q^2+p^2+q^2$

is symmetric in \(p\) and \(q\), and it only involves their squares. Therefore whenever the recurrence produces \((p,q',A')\), the states

$(q',p,A')\qquad \text{and} \qquad (q',-p,A')$

represent valid orientations of the same quadratic surface. The implementation therefore pushes three states:

$(p,q',A'),\qquad (q',p,A'),\qquad (q',-p,A').$

The first one continues the same Pell branch with fixed \(p\). The two swapped states let the new value \(q'\) become the fixed coordinate of later Pell branches. The negative-sign branch is essential: for example, from area \(9\) the state \((4,-1,9)\) leads to the next solution \((4,15,121)\), which corresponds to \((b,c)=(8,30)\).

The repository does not store a separate formal proof of uniqueness for this tree, but it does verify the construction exhaustively against brute force for a small limit and against the statement checkpoint \(S(10^6)=18018206\).

How the Code Works

The C++ file contains both a slow validator and the optimized recurrence solver. The validator iterates over unordered pairs \(b \le c\), uses

$m^2=b^2c^2+b^2+c^2$

and checks whether \(m\) is an even square root. The bounds

$bc \le 2A \le 2L$

justify the scan limit \(b \le 2L\) and the inner bound \(c \lesssim 2L/b\).

The fast solver works in half-coordinates \((p,q)\). Function sum_for_seed performs an explicit depth-first traversal with a stack of states \((p,q,A)\). Function next_state applies the Pell step above, discards branches with \(A' \le 0\) or \(A' > L\), and creates the three follow-up states. The C++ version uses 128-bit intermediates and distributes seeds across threads with an atomic counter; Python relies on arbitrary-precision integers, and Java uses BigInteger for the recurrence arithmetic.

Complexity Analysis

The brute-force validator is roughly

$\sum_{b \le 2L} O\!\left(\frac{L}{b}\right)=O(L\log L),$

which is already too slow for the real limit. The optimized solver is output-sensitive: if \(T(L)\) is the number of generated states whose next area stays within the bound, then the runtime is \(O(T(L))\) arithmetic transitions. Memory is proportional to the active DFS stack size per worker, not to a full \((b,c)\) grid. The important practical improvement is that the search follows only Pell-generated solutions instead of testing almost all integer pairs.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=390
2. Heron's formula: Wikipedia — Heron's formula
3. Pell equation: Wikipedia — Pell's equation
4. Diophantine equation: Wikipedia — Diophantine equation