Detailed mathematical approach

Problem Summary

For a bound \(N\), define

$S(N)=\sum_{\substack{1\le x\le y\le z\le N\\ \gcd(x,y,z)=1\\ 15(x^2+y^2+z^2)=34(xy+yz+zx)}}(x+y+z).$

The task is to evaluate \(S(10^9)\). The C++, Python, and Java implementations do not search directly in \((x,y,z)\)-space. Instead, they generate primitive solutions from a quadratic parametrization, divide out a small class factor, and keep only the parameter pairs that can satisfy the ordering and divisibility conditions.

Mathematical Approach

The key observation is that the ordered primitive triples on this quadratic surface can be generated from coprime pairs \((u,v)\) lying in a narrow cone. The raw quadratic forms are

$x_0=15u^2-34uv+15v^2,\qquad y_0=105u^2-446uv+473v^2,\qquad z_0=32u^2-176uv+240v^2.$

After dividing by a class factor \(g\in\{1,4,16,19,64,76,304,1216\}\), the counted triple is

$x=\frac{x_0}{g},\qquad y=\frac{y_0}{g},\qquad z=\frac{z_0}{g}.$

Step 1: Parametrize the Solution Surface

The three raw forms are chosen so that substituting them into the symmetric Diophantine equation gives an identity:

$15(x_0^2+y_0^2+z_0^2)=34(x_0y_0+y_0z_0+z_0x_0).$

Dividing every coordinate by the same positive factor preserves the equation, so the same relation holds for \((x,y,z)\). The primitive condition is enforced by combining \(\gcd(u,v)=1\) with the systematic removal of the shared class factor \(g\).

Step 2: Restrict to the Branch with \(x\le y\le z\)

Write \(t=u/v\). Then

$x_0=v^2(15t^2-34t+15)=v^2(5t-3)(3t-5).$

To obtain positive solutions on the relevant branch we need \(t>5/3\). Next,

$y_0-x_0=2v^2(45t^2-206t+229).$

The smaller root of \(45t^2-206t+229=0\) is

$h=\frac{103-4\sqrt{19}}{45}.$

Therefore \(x_0\le y_0\) on the ordered branch when

$\frac{5}{3}<t\le h.$

On this same interval one also has \(y_0\le z_0\), so the search only needs the cone

$\frac{5}{3}v<u\le hv.$

Step 3: Extract the Common Class Factor

Introduce the linear forms

$a=5u-3v,\qquad b=3u-5v.$

Then the raw coordinates can be rewritten as

$x_0=ab,$

$y_0=\frac{(3a-19b)(a-5b)}{4},$

$z_0=\frac{(5a-19b)(a-3b)}{4}.$

These identities explain why only eight class factors occur. The \(2\)-power part is

$g_2=4^{\min(\nu_2(a),\nu_2(b),3)},$

so \(g_2\in\{1,4,16,64\}\). In addition, if \(19\mid a\), then all three raw coordinates are divisible by \(19\). Hence the full factor is one of

$g\in\{1,4,16,64\}\times\{1,19\}=\{1,4,16,19,64,76,304,1216\}.$

Step 4: Turn Divisibility into a Residue Table Modulo \(304\)

The class factor depends only on

$a\bmod 16,\qquad b\bmod 16,\qquad a\bmod 19.$

That is enough because the \(2\)-power part only needs the powers of \(2\) in \(a\) and \(b\) up to \(2^3\), and the \(19\)-part only asks whether \(a\equiv 0\pmod{19}\). Combining modulus \(16\) and modulus \(19\) gives

$16\cdot 19=304.$

So for each class factor \(g\) and each residue of \(v\bmod 304\), the implementations precompute the admissible residues of \(u\bmod 304\). The main search can then skip every parameter pair whose residue class cannot possibly land in the desired primitive branch.

Step 5: Bound the Search by \(z\le N\)

Still writing \(t=u/v\), we have

$z_0=v^2(32t^2-176t+240).$

On the interval \(\frac{5}{3}<t\le h\), this quadratic factor is minimized at the right endpoint, so

$z_0\ge c_{\min}v^2,\qquad c_{\min}=32h^2-176h+240.$

Because the counted triple satisfies \(z=z_0/g\le N\), every class obeys

$v\le \sqrt{\frac{Ng}{c_{\min}}}.$

This square-root bound is exactly what determines the per-class outer loop limits.

Worked Example

Take \((u,v)=(13,7)\). Then

$\frac{u}{v}=\frac{13}{7}\approx 1.857,$

which lies inside \(\frac{5}{3}<u/v\le h\). Now

$a=5u-3v=44,\qquad b=3u-5v=4.$

Both \(a\) and \(b\) are divisible by \(4\), but not both by \(8\), so \(g_2=16\). Since \(19\nmid 44\), there is no extra factor \(19\), hence \(g=16\).

The raw forms are

$x_0=176,\qquad y_0=336,\qquad z_0=1152,$

and dividing by \(16\) gives

$ (x,y,z)=\left(11,21,72\right). $

This triple is primitive and ordered, and it satisfies

$15(11^2+21^2+72^2)=34(11\cdot21+21\cdot72+72\cdot11).$

Its contribution to the sum is therefore

$11+21+72=104.$

How the Code Works

The C++, Python, and Java implementations all follow the same pipeline. First they precompute, for each class factor and each residue of \(v\bmod 304\), the admissible residues of \(u\bmod 304\). Next they determine class-dependent upper bounds for \(v\) from the inequality \(z\le N\). For every \(v\), they scan only the integers \(u\) in the cone \(\frac{5}{3}v<u\le hv\) that match one of the allowed residue classes. They then apply three final filters: \(\gcd(u,v)=1\), the bound \(z_0\le Ng\), and division by the class factor \(g\). Every surviving candidate contributes

$\frac{x_0+y_0+z_0}{g}$

to the running total. The C++ and Java implementations optionally split the \(v\)-range across several threads for large \(N\); the Python implementation uses the same arithmetic in a single thread.

Complexity Analysis

The residue precomputation is constant-size, because it only fills tables for \(8\) classes and \(304\) residues. For a fixed class, the outer variable \(v\) runs to \(O(\sqrt{N})\), while the raw width of the cone in \(u\) is \(O(v)\). Thus the unfiltered search region has \(O(N)\) area. The residue table removes most candidates before any gcd or bound test is attempted, so the practical constant factor is much smaller than a direct cone scan. Memory usage is \(O(1)\) apart from the small residue tables and, in the threaded implementations, one accumulator per worker.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=785
2. Diophantine equation: Wikipedia — Diophantine equation
3. Binary quadratic form: Wikipedia — Binary quadratic form
4. Modular arithmetic: Wikipedia — Modular arithmetic
5. Greatest common divisor: Wikipedia — Greatest common divisor