Detailed mathematical approach

Problem Summary

We seek the number of integers \(n \lt 5 \times 10^7\) for which the equation \(x^2 - y^2 - z^2 = n\) has exactly one solution in positive integers, under the extra condition that \(x\), \(y\), and \(z\) are consecutive terms of an arithmetic progression. Because the progression condition ties the three variables together, the real task is not an unrestricted three-variable search but a structured counting problem over admissible factorizations of \(n\).

The C++, Python, and Java implementations do not test each \(n\) separately. Instead they enumerate every valid progression once, convert it into the corresponding value of \(n\), and keep only the information needed to distinguish “zero solutions”, “one solution”, and “more than one solution”.

Mathematical Approach

The key step is to rewrite the arithmetic progression in terms of its middle term and common difference, then convert the resulting quadratic expression into a product with simple congruence and inequality constraints.

Using the Middle Term of the Progression

If \(x\), \(y\), and \(z\) are in arithmetic progression with positive common difference \(d\), then we may write

$x = y + d,\qquad z = y - d,\qquad d \ge 1,\qquad y \gt d.$

Substituting into the equation gives

$n = (y+d)^2 - y^2 - (y-d)^2 = 4yd - y^2 = y(4d-y).$

So every solution is encoded by a positive middle term \(y\) and a second positive integer \(4d-y\).

Turning the Equation into Constrained Factor Pairs

Introduce the variables

$u = y,\qquad v = 4d-y.$

Then the equation becomes simply

$n = uv.$

This transformation is reversible. From an admissible pair \((u,v)\) we recover

$d = \frac{u+v}{4},\qquad x = u+d = \frac{5u+v}{4},\qquad z = u-d = \frac{3u-v}{4}.$

Therefore a pair \((u,v)\) corresponds to a valid solution exactly when

$u \ge 1,\qquad v \ge 1,\qquad u+v \equiv 0 \pmod 4,$

and, because \(z \gt 0\),

$\frac{u+v}{4} \lt u \qquad\Longleftrightarrow\qquad v \lt 3u.$

So the number of representations of \(n\) is precisely the number of factor pairs \((u,v)\) satisfying

$uv=n,\qquad u+v \equiv 0 \pmod 4,\qquad 1 \le v \lt 3u.$

Why This Is a Bijection

Starting from a progression solution, the formulas above produce one admissible pair \((u,v)\). Starting from an admissible pair, the inverse formulas produce integers \(d\), \(x\), and \(z\), and the inequalities guarantee \(d \ge 1\) and \(z \gt 0\). No two different admissible pairs generate the same triple, so counting solutions to the original equation is exactly the same as counting these constrained factorizations.

That is the decisive simplification: a quadratic Diophantine problem in three variables becomes a sieve over products \(uv\) with one modular condition and one linear bound.

Worked Examples: One Singleton and One Non-Singleton

For \(n=3\), the admissible factorizations are extremely limited. The pair \((u,v)=(3,1)\) satisfies \(uv=3\), \(u+v=4\), and \(v\lt 3u\). Then

$d=\frac{3+1}{4}=1,\qquad (x,y,z)=(4,3,2).$

No other factor pair of 3 passes the same tests, so \(n=3\) is counted.

For \(n=15\), however, there are two admissible pairs: \((u,v)=(3,5)\) and \((u,v)=(5,3)\). They lead to the two progressions

$ (x,y,z)=(5,3,1),\qquad (x,y,z)=(7,5,3). $

Thus 15 does not qualify for Problem 136, because its number of solutions is 2 rather than 1.

From the Formula to a Sieve

Once the representation count is rephrased in terms of \((u,v)\), the algorithm is natural. For each positive \(u\), every admissible \(v\) must satisfy

$v \le \left\lfloor\frac{N-1}{u}\right\rfloor$

to keep \(n=uv\) below the limit \(N=5\times 10^7\), and also

$v \le 3u-1$

because \(v\lt 3u\) and \(v\) is integral. The congruence \(u+v\equiv 0\pmod 4\) means that valid values of \(v\) form a single arithmetic progression modulo 4. So for each \(u\), the implementation jumps directly through the compatible \(v\)-values, marks the product \(uv\), and increases its representation count.

Because the problem only asks whether the count is exactly 1, there is no reason to store large multiplicities. As soon as a value of \(n\) has been seen twice, it is already known not to be a singleton, so the stored count can be saturated at 2.

How the Code Works

Enumerating Admissible Products

The C++, Python, and Java implementations allocate a counter table for \(0,1,\dots,N-1\), where \(N=5\times 10^7\). They then loop over every positive candidate for the middle term and compute the largest companion factor allowed by the product bound and the inequality \(v\lt 3u\).

For each fixed middle term, the first compatible companion factor is the smallest positive integer in the residue class \(v \equiv -u \pmod 4\). Advancing by 4 preserves the integrality of \(d=(u+v)/4\), so every loop iteration corresponds to one genuine arithmetic progression solution. The value \(n=uv\) is formed and the counter for that \(n\) is increased, but only up to 2.

Why a Byte-Sized Counter Is Enough

The implementations do not need the exact number of representations once it exceeds 1. They only need to distinguish the three states “not seen yet”, “seen exactly once”, and “seen at least twice”. That is why a byte-sized table is enough even at the full bound: each cell stores a tiny saturated count rather than an unrestricted integer.

Final Scan and a Small Sanity Check

After the sieve phase, the algorithm performs one linear pass through the table and counts how many entries are equal to 1. That total is the required answer.

One implementation also includes a small checkpoint: below 100 there are 25 qualifying values. This is a useful sanity check because it validates the derivation and the congruence logic before the full \(5\times 10^7\) computation is attempted.

Complexity Analysis

Let \(N\) be the search bound. For a fixed \(u\), the number of admissible companion factors is

$O\!\left(\min\!\left(u,\frac{N}{u}\right)\right),$

up to the constant factor coming from the step size 4. Summing over all \(u\) gives

$\sum_{u=1}^{N-1} O\!\left(\min\!\left(u,\frac{N}{u}\right)\right)=O(N\log N).$

So the sieve phase runs in \(O(N\log N)\) time, and the final pass over the counter table is \(O(N)\). The memory usage is \(O(N)\) bytes for the saturated counter array. At \(N=5\times 10^7\), that is large but still practical in the compiled implementations, and it is exactly why the algorithm avoids storing full solution lists.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=136
2. Arithmetic progression: Wikipedia - Arithmetic progression
3. Diophantine equation: Wikipedia - Diophantine equation
4. Modular arithmetic: Wikipedia - Modular arithmetic
5. Divisor and factor pairs: Wikipedia - Divisor