Detailed mathematical approach

Problem Summary

We want to count integer-sided triangles \((a,b,c)\) with \(a \le b \le c\), perimeter \(a+b+c \le P\), and

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

For the Project Euler instance, \(P=25{,}000{,}000\). The equation says that the triangle is exactly one unit away from being right-angled, so a brute-force search over all triples is completely impractical.

The successful idea is to fix the smallest side \(a\), rewrite the equation as a factorization of \(a^2-1\), and count only the divisor pairs that can still satisfy the perimeter and ordering constraints.

Mathematical Approach

The central observation is that once \(a\) is fixed, the other two sides can be recovered from a factor pair of \(a^2-1\). That turns the problem from a quadratic search in \((b,c)\) into a bounded divisor-counting problem.

Fix the smallest side first

Because \(a \le b \le c\), every valid triangle satisfies

$3a \le a+b+c \le P.$

Therefore

$1 \le a \le \left\lfloor \frac{P}{3}\right\rfloor.$

The implementations loop over this range of possible smallest sides and solve the rest of the triangle from there.

Rewrite the equation as a product

Start from

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

which can be rearranged as

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

Now define

$u=b+c,\qquad v=c-b.$

Then \(u>0\), \(v\ge 0\), and

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

Conversely, once a factor pair \((u,v)\) is known, the two larger sides are

$b=\frac{u-v}{2},\qquad c=\frac{u+v}{2}.$

So for a fixed \(a\), every admissible triangle corresponds to a divisor pair of \(a^2-1\) with the parity condition

$u\equiv v \pmod 2,$

because \(b\) and \(c\) must be integers.

For \(a \ge 2\), we have \(a^2-1>0\), so \(v>0\). Then each valid choice of the smaller factor \(v\) determines \(u=(a^2-1)/v\), and therefore determines \((b,c)\) uniquely.

Turn the triangle conditions into bounds on one divisor

The perimeter becomes especially simple in the new variables:

$a+b+c=a+u.$

Hence the perimeter bound is

$u \le P-a.$

Since \(u=(a^2-1)/v\), this gives the lower bound

$v \ge v_{\min}=\left\lceil\frac{a^2-1}{P-a}\right\rceil.$

Very small divisors make \(u\) too large, so they cannot contribute.

The ordering condition \(a \le b\) becomes

$a \le \frac{u-v}{2}\qquad\Longleftrightarrow\qquad u \ge v+2a.$

Substituting \(u=(a^2-1)/v\) yields

$v^2+2av \le a^2-1.$

Solving this quadratic inequality gives an upper bound for the smaller factor:

$v \le v_{\max}=\left\lfloor \sqrt{2a^2-1}-a\right\rfloor.$

Therefore the search for \(v\) is completely localized:

$v_{\min} \le v \le v_{\max},\qquad v \mid (a^2-1).$

Only divisors of \(a^2-1\) inside this interval need to be tested.

Once this upper bound is enforced, the strict triangle inequality no longer needs a separate filter. Indeed,

$a+b-c=a-v,$

and the bound above implies \(v<a\). So every divisor that survives the bound and parity checks already yields a genuine triangle with \(a \le b \le c\).

The exceptional family \(a=1\)

When \(a=1\), the product \(a^2-1\) vanishes, so the divisor parameterization above is not the right tool. The original equation becomes

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

which immediately simplifies to \(b=c\). So every triangle in this family has the form

$ (1,b,b).$

The perimeter condition is then

$1+2b \le P,$

so this case contributes exactly

$\left\lfloor \frac{P-1}{2}\right\rfloor$

solutions and is counted separately before the main divisor loop.

Worked example

Take \(a=5\). Then

$a^2-1=24.$

The upper bound from \(a \le b\) is

$v_{\max}=\left\lfloor \sqrt{49}-5\right\rfloor=2.$

So only the divisors \(v=1\) and \(v=2\) are even worth examining.

For \(v=1\), we get \(u=24\), but \(u-v=23\) is odd, so \(b\) and \(c\) would not be integers. For \(v=2\), we get \(u=12\), hence

$b=\frac{12-2}{2}=5,\qquad c=\frac{12+2}{2}=7.$

This produces the valid almost-right triangle \((5,5,7)\), and indeed

$5^2+5^2=7^2+1.$

The full algorithm repeats exactly this bounded divisor test for every \(a \le P/3\).

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical plan. They first set \(a_{\max}=\lfloor P/3\rfloor\), add the separate contribution from \(a=1\), and build a smallest-prime-factor table up to \(a_{\max}+1\). That range is enough because the implementations never factor \(a^2-1\) directly. Instead they factor \(a-1\) and \(a+1\), then combine those prime exponents to recover the factorization of \((a-1)(a+1)=a^2-1\).

For each fixed \(a \ge 2\), the implementation computes \(v_{\min}\) from the perimeter bound and an initial floating-point estimate of \(v_{\max}\) from \(\sqrt{2a^2-1}-a\). Because floating-point rounding can miss the true floor by one, that estimate is corrected with exact integer inequalities before any counting starts. After that, the implementation generates only those divisors of \(a^2-1\) that do not exceed \(v_{\max}\), and each candidate \(v\) is checked against the four remaining conditions: \(v \ge v_{\min}\), correct parity, \(u \ge v+2a\), and \(a+u \le P\).

The work splits naturally across independent ranges of \(a\). The C++ and Java implementations distribute consecutive chunks of \(a\)-values to worker threads, while the Python implementation uses the same chunking idea with worker processes when that helps and falls back to a serial pass otherwise. Each worker needs only small temporary factor and divisor buffers, so the main shared structure is the prime-factor table.

Complexity Analysis

The smallest-prime-factor table up to \(a_{\max}+1=\lfloor P/3\rfloor+1\) costs \(O(P)\) time and \(O(P)\) memory up to constant factors. After that, the work for one fixed \(a\) is dominated by factoring \(a-1\) and \(a+1\) and by generating the admissible divisors of \(a^2-1\).

A convenient summary of the total runtime is

$O\!\left(P+\sum_{a\le P/3}\tau(a^2-1)\right),$

where \(\tau(n)\) is the divisor-counting function. This matches the structure of the implementations: the sieve is linear-size preprocessing, and the main loop spends its time on the divisor structure of \(a^2-1\). Parallel execution improves wall-clock time but does not change the asymptotic bound. Extra memory beyond the sieve is only small thread-local or process-local working storage.

Footnotes and References

1. Problem page: Project Euler 223 - Almost Right-angled Triangles I
2. Integer triangles: Wikipedia - Integer triangle
3. Diophantine equations: Wikipedia - Diophantine equation
4. Difference of two squares: Wikipedia - Difference of two squares
5. Fast factorization with a smallest-prime-factor sieve: cp-algorithms - Integer factorization