Detailed mathematical approach

Problem Summary

We want the number of integer-sided triangles \((a,b,c)\) with perimeter at most \(75{,}000{,}000\) such that

$a^2+b^2=c^2-1.$

Equivalently, \(c^2=a^2+b^2+1\), so the longest side is only one unit of square-length beyond the right-triangle relation. By the law of cosines, the angle opposite \(c\) satisfies

$\cos C=\frac{a^2+b^2-c^2}{2ab}=-\frac{1}{2ab},$

which explains the title: the triangle is obtuse, but only barely.

Mathematical Approach

The fast solution does not scan all possible side lengths. Instead it walks through a ternary tree of integer triples that preserves the quadratic form

$Q(a,b,c)=c^2-a^2-b^2.$

Basic arithmetic structure of the equation

Once \(a\) and \(b\) are positive, the triangle inequality is automatic. Indeed,

$c^2=a^2+b^2+1 \lt a^2+b^2+2ab=(a+b)^2,$

so \(c \lt a+b\). The code still checks \(a+b \gt c\), but mathematically every positive solution already gives a genuine triangle.

The parity is also forced. Squares are \(0\) or \(1\) modulo \(4\), so

$a^2+b^2+1\equiv c^2 \pmod 4$

rules out the cases where one of \(a,b\) is odd or both are odd. Therefore every solution has

$a\equiv b\equiv 0 \pmod 2,\qquad c\equiv 1 \pmod 2.$

The smallest positive solution is then \((2,2,3)\).

The three invariant-preserving transformations

Write a triple as the column vector \(t=(a,b,c)^T\). The implementations repeatedly apply the three matrices

$M_1=\begin{pmatrix}1&-2&2\\2&-1&2\\2&-2&3\end{pmatrix},\qquad M_2=\begin{pmatrix}1&2&2\\2&1&2\\2&2&3\end{pmatrix},\qquad M_3=\begin{pmatrix}-1&2&2\\-2&1&2\\-2&2&3\end{pmatrix}.$

If \(G=\mathrm{diag}(-1,-1,1)\), then \(Q(t)=t^T G t\), and each matrix satisfies

$M_i^T G M_i=G.$

So every transform preserves \(Q\):

$Q(M_i t)=Q(t).$

Since the root triple \((2,2,3)\) has \(Q=1\), every descendant automatically satisfies \(c^2-a^2-b^2=1\), or equivalently \(a^2+b^2=c^2-1\).

Root triple, symmetry, and completeness of the tree

The search starts from

$(2,2,3),$

the smallest positive point on \(Q=1\). The three matrices above form a Berggren-type tree for this quadratic form: keeping orientation, repeated application generates the positive integer solutions without duplicates. The implementation relies on that structure, and the C++ version also confirms it against direct enumeration for several small perimeter bounds.

The equation is symmetric in \(a\) and \(b\), but the tree is built on ordered triples. To count each geometric triangle once, the algorithm uses the canonical orientation

$a\le b.$

That test is applied only when counting, not when traversing, because an intermediate state with \(a\gt b\) can still lead to later descendants with \(a\le b\).

Worked example: why mirror states still matter

Applying the three matrices to the root gives

$M_1(2,2,3)^T=(4,8,9)^T,\qquad M_2(2,2,3)^T=(12,12,17)^T,\qquad M_3(2,2,3)^T=(8,4,9)^T.$

All three satisfy

$a^2+b^2+1=c^2.$

The third child is not counted immediately because \(8\gt 4\). Nevertheless it cannot be discarded. Applying \(M_1\) once more gives

$M_1(8,4,9)^T=(18,30,35)^T,$

and now \(18\le 30\), so this branch contributes a new valid triangle. This is why the traversal keeps both orientations even though counting uses only one orientation.

Why the perimeter bound gives a finite search

The third coordinate of each child is

$c_1=2a-2b+3c,\qquad c_2=2a+2b+3c,\qquad c_3=-2a+2b+3c.$

Because

$c^2=a^2+b^2+1\gt (a-b)^2,$

we have \(c\gt |a-b|\). Therefore

$c_1=c+2(a-b+c)\gt c,\qquad c_2\gt c,\qquad c_3=c+2(b-a+c)\gt c.$

So the tree always moves toward larger triples. Once a node has perimeter \(a+b+c\gt P\), every deeper descendant is even larger, so a depth-first search with perimeter pruning visits exactly the finite portion of the tree that matters. In other words, the answer is

$T(P)=\#\{(a,b,c)\in\mathcal{T}: a+b+c\le P,\ a\le b\},$

where \(\mathcal{T}\) is the ternary tree generated from \((2,2,3)\) by \(M_1,M_2,M_3\).

How the Code Works

Iterative tree traversal

The C++, Python, and Java implementations perform an explicit depth-first search. They begin with the root triple \((2,2,3)\) on a stack, pop one triple at a time, compute its perimeter, and discard it immediately if the perimeter exceeds the limit.

If the node survives that test, the implementation increments the answer when \(a\le b\) and \(a+b\gt c\). The second condition is mathematically redundant for positive solutions of this equation, but keeping it in the code makes the intended triangle filter completely explicit.

Each visited node is then multiplied by the three fixed matrices. Children with any nonpositive coordinate are rejected, and children already above the perimeter limit are not pushed. Because the invariant \(c^2-a^2-b^2=1\) is preserved by construction, the fast path never needs a square-root check.

Checkpoint verification

The C++ implementation also contains a direct verifier for several small perimeter values. That slower routine enumerates \(a\le b\), reconstructs \(c\) from \(a^2+b^2+1\), tests whether \(c\) is an integer, and compares the result with the tree-based count. Matching on those checkpoints is strong evidence that the matrix tree and the counting rule are aligned correctly before the large bound is used.

Complexity Analysis

Let \(N(P)\) be the number of generated tree nodes with perimeter at most \(P\). Every visited node costs only constant work: one perimeter computation, one counting test, and three fixed \(3\times 3\) matrix applications. Therefore the running time is

$O(N(P)).$

This is output-sensitive: it depends on how many almost-right triangles actually exist below the perimeter bound, not on the much larger search box \(1\le a,b,c\le P\). The explicit DFS stack stores only the current frontier of a constant-branching tree, so the auxiliary memory is \(O(D(P))\), where \(D(P)\) is the maximum depth reached under the perimeter limit.

Footnotes and References

1. Project Euler problem page: Problem 224 - Almost Right-angled Triangles II
2. Law of cosines: Wikipedia - Law of cosines
3. Quadratic form: Wikipedia - Quadratic form
4. Diophantine equation: Wikipedia - Diophantine equation
5. Pythagorean triples and Berggren-style trees: Wikipedia - Pythagorean triple