Detailed mathematical approach

Problem Summary

For each shift \(k\) with \(0\le k\le m\), let \(P_k(n)\) be the number of unordered primitive positive integer triples \((p,q,r)\) such that

$p^2+q^2+k=r^2,\qquad p+q+r\le n,\qquad \gcd(p,q,r)=1.$

The required quantity is

$S(m,n)=\sum_{k=0}^{m} P_k(n).$

A brute-force scan over all triples up to the perimeter bound would be far too slow, so the implementation organizes the search through a finite set of roots and a tree of shift-preserving linear transformations.

Mathematical Approach

Fix one value of \(k\), and define the quadratic form

$Q(p,q,r)=r^2-p^2-q^2.$

Then the triples relevant to this shift are exactly the primitive positive integer points on the level set \(Q(p,q,r)=k\).

Step 1: Use transformations that preserve the shift

The search is built from three linear maps:

$A(p,q,r)=\bigl(p-2q+2r,\ 2p-q+2r,\ 2p-2q+3r\bigr),$

$B(p,q,r)=\bigl(p+2q+2r,\ 2p+q+2r,\ 2p+2q+3r\bigr),$

$C(p,q,r)=\bigl(-p+2q+2r,\ -2p+q+2r,\ -2p+2q+3r\bigr).$

A direct expansion shows that each map preserves the quadratic form:

$Q(A(p,q,r))=Q(B(p,q,r))=Q(C(p,q,r))=Q(p,q,r).$

So if one triple satisfies \(p^2+q^2+k=r^2\), then all of its descendants under these maps satisfy the same equation with the same shift \(k\). The maps are also invertible over the integers, so primitiveness is preserved: any common divisor of a child would also divide its parent.

Step 2: Extract the roots by checking the inverse maps

The inverse transformations are

$A^{-1}(p,q,r)=\bigl(p+2q-2r,\ -2p-q+2r,\ -2p-2q+3r\bigr),$

$B^{-1}(p,q,r)=\bigl(p+2q-2r,\ 2p+q-2r,\ -2p-2q+3r\bigr),$

$C^{-1}(p,q,r)=\bigl(-p-2q+2r,\ 2p+q-2r,\ -2p-2q+3r\bigr).$

A primitive triple is called a root if none of these inverse images has all coordinates positive. Equivalently, a root is a solution with no parent inside the same search forest.

The implementations first enumerate primitive candidates with

$1\le p\le q\le \max(4m,10),$

test whether \(p^2+q^2+k\) is a square, and then discard every candidate that has a positive inverse parent. The underlying solver states that for \(k>0\), every root satisfies \(p,q\le 4k\), so scanning up to \(\max(4m,10)\) covers every shift \(0\le k\le m\).

Step 3: Traverse each rooted component with a perimeter cutoff

Once the roots for a fixed \(k\) are known, each root generates one component under repeated application of \(A\), \(B\), and \(C\). The implementations explore that component with an explicit depth-first stack.

The perimeter function

$\pi(p,q,r)=p+q+r$

provides the pruning rule: if \(\pi(p,q,r)>n\), that node contributes nothing and its branch is discarded. Therefore only triples that can affect \(P_k(n)\) are ever visited.

Because non-roots were removed in the previous step, every admissible triple belongs to exactly one rooted component, so starting DFS from all roots visits each relevant ordered triple exactly once.

Step 4: Convert ordered triples to unordered triples

The equation and the primitiveness condition are unchanged by the swap

$\sigma(p,q,r)=(q,p,r).$

The root search only seeds triples with \(p\le q\), so the component structure already avoids double-starting symmetric families. Inside a component, the implementation records two values:

$T=\text{number of visited triples},\qquad D=\text{number of visited triples with }p=q.$

If the component contains diagonal states \(p=q\), then \(\sigma\) keeps that component, fixes exactly the diagonal states, and pairs all off-diagonal states. The unordered contribution is therefore

$U=\frac{T+D}{2}.$

If no diagonal state appears, the selected rooted component already contributes the correct unordered count, so the implementation simply uses \(U=T\).

Step 5: Worked example for \(k=7\)

The triple \((1,1,3)\) is primitive and satisfies

$1^2+1^2+7=9=3^2,$

so it belongs to the shift \(k=7\). Applying the three transformations gives

$A(1,1,3)=(5,7,9),\qquad B(1,1,3)=(9,9,13),\qquad C(1,1,3)=(7,5,9).$

All three children still satisfy

$r^2-p^2-q^2=7.$

With perimeter bound \(n=31\), exactly four states from this component are counted:

$ (1,1,3),\ (5,7,9),\ (7,5,9),\ (9,9,13). $

Here \(T=4\), and the diagonal states are \((1,1,3)\) and \((9,9,13)\), so \(D=2\). Hence the unordered contribution is

$U=\frac{4+2}{2}=3,$

corresponding to the three unordered triples \((1,1,3)\), \((5,7,9)\), and \((9,9,13)\).

Step 6: Sum over all shifts

After computing the unordered count \(P_k(n)\) for each fixed \(k\), the final result is simply

$S(m,n)=\sum_{k=0}^{m} P_k(n).$

So the full problem is reduced to a finite root search for every shift and a pruned tree traversal from each root.

How the Code Works

The C++, Python, and Java implementations all follow the same counting strategy. For every \(k\), they enumerate candidate primitive triples in the bounded root window, keep only those whose inverse images are not positive, and store those survivors as roots. Then each root is explored with an explicit stack, repeatedly applying the three forward maps and pruning as soon as the perimeter exceeds \(n\).

For every rooted component, the implementation accumulates the total number of visited triples and, separately, the number with \(p=q\). That pair is converted into an unordered contribution using the formula from the previous section. Summing these component contributions yields \(P_k(n)\), and summing \(P_k(n)\) over \(k=0,\dots,m\) gives the final answer. The C++ and Java implementations additionally distribute independent root tasks across worker threads, while the Python implementation delegates to the same underlying search strategy rather than re-deriving different mathematics.

Complexity Analysis

Let \(R_k\) be the number of roots for shift \(k\), and let \(T_k(n)\) be the total number of triples visited across all rooted components after perimeter pruning. The preliminary root scan uses the bounded box

$1\le p\le q\le \max(4m,10),$

so its cost depends only on \(m\), not on the large perimeter bound \(n\). The dominant work is the traversal itself, which gives total running time

$O\!\left(\sum_{k=0}^{m} T_k(n)\right).$

Memory usage is linear in the stored roots plus the explicit DFS stack for the currently explored component. Parallel execution reduces wall-clock time, but it does not change the underlying combinatorial work measured by the same sum of visited states.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=730
2. Pythagorean triple: Wikipedia — Pythagorean triple
3. Tree of primitive Pythagorean triples: Wikipedia — Tree of primitive Pythagorean triples
4. Depth-first search: Wikipedia — Depth-first search
5. Quadratic form: Wikipedia — Quadratic form