Detailed mathematical approach

Problem Summary

Let \(S(N)\) be the sum of \(x+y+z\) over all primitive positive integer solutions of

$z^2=16x^2+y^4,$

with \(\gcd(x,y,z)=1\) and the problem's size bound \(z\le N\). The final result is required modulo \(10^9\). A naive search over \(x\) and \(y\) is far too expensive, so the key task is to describe every primitive solution by a small set of parameters and then iterate only those parameters.

Mathematical Approach

The implementations split the equation into two cases according to the parity of \(y\). Each case leads to a complete parametrization, and the search range becomes a fourth-root range instead of a direct scan over coordinates.

Step 1: Factor the Equation and Split by the Parity of \(y\)

Rearrange the equation as

$(z-4x)(z+4x)=y^4.$

Define

$a=z-4x,\qquad b=z+4x.$

Then \(ab=y^4\), \(a\lt b\), and \(a,b\) have the same parity. The primitive condition strongly limits their common divisor. This is where the parity of \(y\) matters:

If \(y\) is odd, then \(a\) and \(b\) are odd and in fact coprime.

If \(y\) is even, the power of \(2\) inside \(a\) and \(b\) is no longer symmetric, producing a second family.

Step 2: Odd \(y\) Gives the First Parametrization

Assume \(y\) is odd. Then \(y^4\) is odd, so both \(a\) and \(b\) are odd. Any common divisor \(d\) of \(a\) and \(b\) also divides

$b-a=8x,\qquad a+b=2z.$

Because \(d\) is odd, it must divide both \(x\) and \(z\). Since \(d\mid ab=y^4\), it also divides \(y\). Therefore \(d\mid \gcd(x,y,z)\), so primitiveness forces \(d=1\).

Now \(a\) and \(b\) are coprime and their product is a fourth power, so each factor must itself be a fourth power. Write

$a=p^4,\qquad b=q^4,$

with \(p\) and \(q\) positive, odd, coprime, and \(p\lt q\). Solving

$z-4x=p^4,\qquad z+4x=q^4$

gives

$x=\frac{q^4-p^4}{8},\qquad y=pq,\qquad z=\frac{p^4+q^4}{2}.$

These formulas are exactly the first branch used by the implementation.

Step 3: Even \(y\) Gives the Second Parametrization

Now assume \(y\) is even. In a primitive solution, \(x\) cannot be even, otherwise \(z\) would also be even and the gcd would be at least \(2\). So \(x\) is odd. Since \(y^4\) is divisible by \(16\), the equation shows that \(z\) is divisible by \(4\). Write

$z=4u,\qquad y=2w.$

Then

$u^2=x^2+w^4.$

If \(w\) were odd, then \(x^2\equiv1\pmod{16}\) and \(w^4\equiv1\pmod{16}\), which would force \(u^2\equiv2\pmod{16}\), impossible. Hence \(w\) is even, so we may write

$y=4t,\qquad z=4u,$

and the equation becomes

$(u-x)(u+x)=16t^4.$

Because \(u\) and \(x\) are odd, both factors are even. Their difference is \(2x\), which is divisible by \(2\) but not by \(4\), so the common power of \(2\) is exactly one factor \(2\). After ordering the factors, we must have

$u+x=2s^4,\qquad u-x=8r^4,$

or the same equations with the two sides swapped. Here \(r\) and \(s\) are coprime, and \(s\) must be odd. Adding and subtracting gives

$x=\left|s^4-4r^4\right|,\qquad t=rs,\qquad z=4\left(s^4+4r^4\right).$

Since \(y=4t\), we obtain the second family

$x=\left|s^4-4r^4\right|,\qquad y=4rs,\qquad z=4\left(s^4+4r^4\right),$

with \(s\) odd and \(\gcd(r,s)=1\). The absolute value simply accounts for which of \(u-x\) and \(u+x\) receives the factor \(8\).

Step 4: Turn the Size Bound into Fourth-Root Bounds

The parametrizations are only useful if their parameter ranges are tight. The bound on \(z\) gives clean fourth-root limits.

For the first family,

$z=\frac{p^4+q^4}{2}\le N.$

Therefore \(q^4\le 2N\), so

$q\le \left\lfloor(2N)^{1/4}\right\rfloor.$

For each fixed odd \(q\), the remaining bound is

$p^4\le 2N-q^4,\qquad p\lt q,$

so the implementation chooses the largest admissible odd \(p\) from those two constraints.

For the second family,

$z=4\left(s^4+4r^4\right)\le N.$

This implies

$s^4\le \frac N4,\qquad r^4\le \frac{N/4-s^4}{4}.$

Hence

$s\le \left\lfloor\left(\frac N4\right)^{1/4}\right\rfloor,\qquad r\le \left\lfloor\left(\frac{N/4-s^4}{4}\right)^{1/4}\right\rfloor.$

So both branches are searched in fourth-root sized loops instead of scanning all \(x\) and \(y\).

Step 5: Worked Example for \(N=100\)

The small checkpoint \(S(100)=81\) follows immediately from the two families.

In the first family, \(q\le \lfloor 200^{1/4}\rfloor=3\). The only admissible odd coprime pair with \(p\lt q\) is \((p,q)=(1,3)\), which gives

$x=\frac{3^4-1^4}{8}=10,\qquad y=1\cdot3=3,\qquad z=\frac{1^4+3^4}{2}=41.$

Its contribution is

$10+3+41=54.$

In the second family, \(s\le \lfloor 25^{1/4}\rfloor=2\), so the only odd choice is \(s=1\). Then \(r=1\) is the only admissible value, giving

$x=\left|1^4-4\cdot1^4\right|=3,\qquad y=4\cdot1\cdot1=4,\qquad z=4(1+4)=20.$

Its contribution is

$3+4+20=27.$

Therefore

$S(100)=54+27=81,$

which matches the small exact check used by the implementation.

Step 6: Final Summation Viewpoint

If we denote the two admissible parameter sets by

$\mathcal{A}_N=\left\{(p,q): p,q\text{ odd},\ 1\le p\lt q,\ \gcd(p,q)=1,\ \frac{p^4+q^4}{2}\le N\right\}$

and

$\mathcal{B}_N=\left\{(r,s): s\text{ odd},\ r\ge1,\ \gcd(r,s)=1,\ 4\left(s^4+4r^4\right)\le N\right\},$

then the desired sum is

$S(N)=\sum_{(p,q)\in\mathcal{A}_N}\left(\frac{q^4-p^4}{8}+pq+\frac{p^4+q^4}{2}\right)+\sum_{(r,s)\in\mathcal{B}_N}\left(\left|s^4-4r^4\right|+4rs+4\left(s^4+4r^4\right)\right).$

The two sums are disjoint because the first family always has odd \(y\), while the second always has \(y\) divisible by \(4\).

How the Code Works

The C++, Python, and Java implementations all follow the same structure. First they compute exact integer fourth roots. Each version starts from a floating-point estimate and then corrects it upward or downward with integer comparisons, so boundary cases remain exact.

Next, the first branch iterates over odd \(q\), derives the largest legal odd \(p\), filters by \(\gcd(p,q)=1\), and forms the triple from the odd-\(y\) parametrization. The second branch iterates over odd \(s\), derives the largest legal \(r\), filters by \(\gcd(r,s)=1\), and forms the triple from the even-\(y\) parametrization. In both branches the code still checks the generated coordinates against the problem bound before adding the contribution.

The final accumulation adds \(x+y+z\) modulo \(10^9\). One implementation also keeps small exact checkpoints and compares a tiny bound against direct enumeration, which confirms that the parametrized search matches brute force on test cases where brute force is still feasible.

Complexity Analysis

The outer parameters \(q\) and \(s\) run only up to \(O(N^{1/4})\). For each outer value, the inner parameter range is also fourth-root sized, so the total number of candidate parameter pairs across both families is \(O(N^{1/2})\). Each candidate requires only a few arithmetic operations and one gcd computation, so the runtime is near \(O(N^{1/2})\) arithmetic steps, or \(O(N^{1/2}\log N)\) if gcd cost is counted explicitly. Memory usage is \(O(1)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=764
2. Diophantine equation: Wikipedia — Diophantine equation
3. Coprime integers: Wikipedia — Coprime integers
4. Greatest common divisor: Wikipedia — Greatest common divisor
5. Pythagorean triple: Wikipedia — Pythagorean triple
6. Integer square root: Wikipedia — Integer square root