Detailed mathematical approach

Problem Summary

The goal is to sum the perimeters of all Fortunate triangles whose perimeter does not exceed \(P_{\max}=10^7\). The C++, Python, and Java implementations do not enumerate triangles by side lengths. Instead, they enumerate primitive solutions of an equivalent quadratic condition, reconstruct actual triangle sides from that data, and then add the contribution of every scaled copy in a single arithmetic-series step.

So the computation has two layers. First, characterize the primitive Fortunate triangles through a parameterized Diophantine surface. Then, once a primitive perimeter \(\Pi\) is known, count every triangle with perimeter \(\Pi,2\Pi,3\Pi,\dots\le P_{\max}\) without generating those multiples one by one.

Mathematical Approach

All three implementations use the same derivation. They reduce the problem to the quadratic identity \(p^2-q^2=15t^2\), classify the compatible squarefree factor pairs, and recover up to two primitive triangles from each coprime parameter pair.

From the Fortunate Condition to a Product Formula

After rewriting the defining relation used by the implementations, every primitive candidate is described by positive integers \(p>q>0\) and \(t>0\) satisfying

$p^2-q^2=15t^2.$

Because

$p^2-q^2=(p+q)(p-q),$

it is natural to define

$S=p+q,\qquad D=p-q.$

Then

$SD=15t^2,\qquad p=\frac{S+D}{2},\qquad q=\frac{S-D}{2}.$

This already explains two hard filters in the search. We need \(D<S\) so that \(q>0\), and \(S\) and \(D\) must have the same parity so that \(p\) and \(q\) are integers.

Why the Search Splits into Exactly Eight Coefficient Families

The implementations write the factor pair \((S,D)\) as square multiples

$S=\kappa m^2,\qquad D=\ell n^2,$

with \(m,n\ge 1\) and \(\gcd(m,n)=1\). Substituting into \(SD=15t^2\) gives

$15t^2=\kappa\ell\,m^2n^2.$

So the squarefree part of \(\kappa\ell\) must be \(15\). In the odd case this leaves exactly the four divisor pairs of \(15\):

$ (1,15),\ (3,5),\ (5,3),\ (15,1). $

But \(S\) and \(D\) must have matching parity. For these four odd families that forces both \(m\) and \(n\) to be odd. The even alternative is to double both coefficients, which preserves the squarefree kernel after removing the necessary factor of \(2\). That produces the four companion families

$ (2,30),\ (6,10),\ (10,6),\ (30,2). $

These eight ordered pairs are exactly the families hard-coded in the implementations.

They also determine \(t\) explicitly. If \(\kappa\ell=15\), then \(t=mn\). If \(\kappa\ell=60\), then \(t=2mn\). The implementations still verify this with an exact integer-square-root check instead of relying only on symbolic reasoning.

Reconstructing the Two Branches of Candidate Triangles

Once \(p\), \(q\), and \(t\) are known, the quadratic data yields two possible side seeds:

$ (p,\ q+t,\ t) \qquad\text{and}\qquad (p,\ q-t,\ t). $

The second branch exists only when \(q>t\), otherwise one side would be zero or negative. At this stage the entries are still not the final triangle sides. The implementations apply a fixed power-of-two normalization: choose the smallest \(\lambda\in\{0,1,2\}\) such that after multiplying the whole seed by \(2^\lambda\), the first two entries are both divisible by \(4\). The actual side lengths are then

$ \left(2^{\lambda-2}p,\ 2^{\lambda-2}(q\pm t),\ 2^\lambda t\right). $

This matches the code literally: repeatedly double the seed until the first two entries can be divided by \(4\), then divide only those two entries by \(4\).

Since \(p+q=S\), the perimeter formulas become

$ \Pi_{+}=2^{\lambda-2}(S+5t),\qquad \Pi_{-}=2^{\lambda-2}(S+3t). $

Those closed forms are what make the perimeter cutoff effective. In particular, every accepted triangle satisfies \(\Pi\ge S/4\), so once \(S>4P_{\max}\) the outer loop can stop immediately.

Primitive Filters, Triangle Checks, and Uniqueness

Not every parameterized seed is accepted. The condition \(\gcd(m,n)=1\) removes repeated square multiples at the parameter level, and \(\gcd(p,q,t)=1\) removes non-primitive points on the quadratic surface before branching. After normalization, the final side triple \((a,b,c)\) must still satisfy \(\gcd(a,b,c)=1\).

The geometry is checked through

$a+b+c>2\max(a,b,c),$

which is a compact form of the triangle inequality. The additional ordering constraint

$b\ge c$

prevents mirrored copies from being counted twice. The inner loop also stops as soon as \(D\ge S\), because then \(q\le 0\) and neither branch can produce a positive triangle.

From One Primitive Perimeter to All Its Multiples

If a primitive triangle survives every filter and has perimeter \(\Pi\), then all similar triangles with perimeters \(k\Pi\le P_{\max}\) also contribute. Writing

$Q=\left\lfloor\frac{P_{\max}}{\Pi}\right\rfloor,$

the total addition from that primitive family is

$ \Pi(1+2+\cdots+Q)=\Pi\,\frac{Q(Q+1)}{2}. $

This is why the implementations never enumerate non-primitive triangles individually: one primitive perimeter already determines the whole arithmetic progression of valid multiples.

Worked Example

Take the family \((\kappa,\ell)=(15,1)\) and the coprime pair \((m,n)=(1,1)\). Then

$ S=15,\qquad D=1,\qquad p=\frac{15+1}{2}=8,\qquad q=\frac{15-1}{2}=7. $

Because \(\kappa\ell=15\), we get

$t=mn=1.$

The plus branch starts from \((8,8,1)\). The first two entries are already divisible by \(4\), so \(\lambda=0\), and the normalized triangle is

$ \left(\frac{8}{4},\frac{8}{4},1\right)=(2,2,1), $

with primitive perimeter \(\Pi_{+}=5\).

The minus branch starts from \((8,6,1)\). Here one doubling is needed, so \(\lambda=1\). After normalization we obtain

$ \left(\frac{16}{4},\frac{12}{4},2\right)=(4,3,2), $

with primitive perimeter \(\Pi_{-}=9\).

If the perimeter cap were \(20\) instead of \(10^7\), the first triangle would contribute \(5\cdot 4\cdot 5/2=50\), and the second would contribute \(9\cdot 2\cdot 3/2=27\). This one example shows the two branches, the power-of-two normalization, and the arithmetic-series summation of all multiples.

How the Code Works

Enumeration Phase

The implementations first loop over the eight coefficient families, then over coprime parameter pairs \((m,n)\). The outer loop stops when \(\kappa m^2>4P_{\max}\), because even the smallest possible perimeter is already too large. The inner loop stops when \(\ell n^2\ge \kappa m^2\), which is exactly the point where \(q\le 0\) and no positive triangle can survive.

For each remaining pair, the implementation reconstructs \(p\), \(q\), and \(t\), enforces the parity condition, verifies the square relation with an exact integer square root, and discards non-primitive quadratic data before branching.

Acceptance and Summation

Each of the two branches goes through the same pipeline: positivity check for the second branch, power-of-two normalization, primitivity check for the final side triple, triangle-inequality test, and the ordering constraint that removes symmetric duplicates. Whenever a primitive perimeter \(\Pi\) is accepted, the implementation computes \(Q=\lfloor P_{\max}/\Pi\rfloor\) and adds \(\Pi\,Q(Q+1)/2\) to the running total.

The C++, Python, and Java versions differ only in syntax and library calls. The mathematical objects, the filters, and the accumulation order are the same in all three.

Complexity Analysis

For one fixed coefficient family, the bound \(\kappa m^2\le 4P_{\max}\) gives \(m=O(\sqrt{P_{\max}})\). For each fixed \(m\), the inequality \(\ell n^2<\kappa m^2\) gives \(n=O(m)\). So each family examines \(O(P_{\max})\) parameter pairs, and the number of families is the constant \(8\).

Each candidate uses only constant-time integer arithmetic, gcd computations, parity tests, one exact square-root verification, and a few local branch checks. The total running time is therefore \(O(P_{\max})\), and the extra space usage is \(O(1)\).

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=919
2. Difference of two squares: Wikipedia - Difference of two squares
3. Square-free integer: Wikipedia - Square-free integer
4. Coprime integers: Wikipedia - Coprime integers
5. Integer triangle: Wikipedia - Integer triangle
6. Triangle inequality: Wikipedia - Triangle inequality
7. Arithmetic progression: Wikipedia - Arithmetic progression