Detailed mathematical approach

Problem Summary

We want to count how many integers \(n \lt 10^6\) have exactly ten representations of the form

$x^2-y^2-z^2=n,$

where \(x\), \(y\), and \(z\) are positive integers in arithmetic progression. Because the three numbers are consecutive terms of one progression, they are not independent: once the middle term and the common difference are known, the triple is fixed.

The key step is to convert the quadratic expression into a constrained factorization of \(n\). After that, the problem becomes a sieve over admissible factor pairs rather than a search over triples.

Mathematical Approach

The implementations are built around one exact reformulation: every valid triple corresponds to one ordered factor pair \((u,v)\) of \(n\) satisfying a congruence condition and a positivity bound.

Parameterizing the arithmetic progression

If \(x\), \(y\), and \(z\) are in arithmetic progression, we may write

$x=a+d,\qquad y=a,\qquad z=a-d,$

with integers \(a \ge 1\) and \(d \ge 1\). The positivity of \(z\) forces \(a>d\).

Substituting into the expression gives

$n=(a+d)^2-a^2-(a-d)^2=4ad-a^2=a(4d-a).$

So every solution is encoded by two positive integers: the middle term \(a\) and the quantity \(4d-a\).

Turning the equation into a factorization problem

Define

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

Then the formula becomes simply

$n=uv.$

This already explains why the code counts products instead of recomputing quadratic expressions. The arithmetic progression condition has not disappeared; it has been packed into restrictions on \((u,v)\).

Since \(u+v=a+(4d-a)=4d\), we obtain the congruence

$u+v\equiv 0 \pmod 4.$

Also, \(z=a-d>0\) means \(d<a\). Rewriting \(d=(u+v)/4\), this becomes

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

Therefore every valid solution yields an ordered factor pair \((u,v)\) such that

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

Why these conditions are also sufficient

The correspondence is not just one-way. Suppose \(u\) and \(v\) are positive integers satisfying

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

Set

$a=u,\qquad d=\frac{u+v}{4}.$

The congruence ensures that \(d\) is an integer. Then

$z=a-d=u-\frac{u+v}{4}=\frac{3u-v}{4}>0,$

so the triple is positive, and

$x=a+d,\qquad y=a,\qquad z=a-d$

is indeed an arithmetic progression. Finally,

$a(4d-a)=u\bigl((u+v)-u\bigr)=uv=n.$

Hence the number of representations of \(n\) is exactly the number of ordered factor pairs \((u,v)\) with those two conditions. This is the real counting object used by the implementations.

Worked example: \(n=27\)

The positive factor pairs of \(27\) are

$ (1,27),\ (3,9),\ (9,3),\ (27,1). $

Now apply the two filters.

The congruence \(u+v\equiv 0 \pmod 4\) keeps all four pairs, because each sum is \(28\) or \(12\). The inequality \(v<3u\) removes \((1,27)\) and \((3,9)\), leaving

$ (9,3)\quad\text{and}\quad(27,1). $

These correspond to

$a=9,\ d=3 \Rightarrow (x,y,z)=(12,9,6),$

and

$a=27,\ d=7 \Rightarrow (x,y,z)=(34,27,20).$

Indeed, both give \(x^2-y^2-z^2=27\). So \(27\) has exactly two valid representations.

From the characterization to a sieve

For a fixed search bound \(N\), we only care about products \(uv<N\). Once \(u\) is fixed, the admissible values of \(v\) must satisfy three conditions at once:

$v\equiv -u \pmod 4,$

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

$v\le 3u-1.$

So for each \(u\), the companion factors \(v\) form one arithmetic progression with step \(4\), starting from the smallest positive value congruent to \(-u\) modulo \(4\), and ending at

$\min\left(3u-1,\left\lfloor\frac{N-1}{u}\right\rfloor\right).$

Each admissible pair contributes one representation to the counter of \(n=uv\). After processing all \(u\), the answer is the number of entries whose counter equals \(10\).

How the Code Works

Counting admissible products

The C++, Python, and Java implementations allocate an array of counters indexed by \(n\). They sweep the first factor through all positive values below the limit. For each such value, they compute the largest possible companion factor allowed by the product bound \(uv<10^6\) and by the positivity condition \(v<3u\).

Next, the implementation finds the first positive companion factor in the correct congruence class \(v\equiv -u\pmod 4\). From there it advances by steps of \(4\), so every visited companion factor automatically satisfies the divisibility condition \(u+v\equiv 0\pmod 4\). Each visited pair updates the counter for the product \(uv\).

Extracting the final answer

Once the sieve is complete, the remaining task is a single scan through the counter array. Every index whose counter is exactly \(10\) contributes to the final total.

The three implementations follow the same mathematics and the same iteration pattern. One of them also includes a small built-in checkpoint: for the smaller bound \(n \lt 10000\), the number of targets is \(45\), which is a useful sanity test before solving the full problem.

Complexity Analysis

Let \(N\) be the upper bound, here \(N=10^6\). For a fixed first factor \(u\), the number of tested companion factors is proportional to

$1+\frac{1}{4}\min\left(3u,\frac{N}{u}\right).$

Summing over all \(u\) gives an \(O(N\log N)\) sieve. Intuitively, small values of \(u\) are limited by the product condition \(uv<N\), while large values of \(u\) are limited by the linear bound \(v<3u\); the harmonic part of the sum is what produces the logarithm.

The memory usage is \(O(N)\), because the dominant data structure is the counter array for \(0\) through \(N-1\). No large auxiliary tables are needed.

Footnotes and References

1. Project Euler, Problem 135: https://projecteuler.net/problem=135
2. Arithmetic progression: Wikipedia - Arithmetic progression
3. Diophantine equation: Wikipedia - Diophantine equation
4. Modular arithmetic: Wikipedia - Modular arithmetic
5. Divisor: Wikipedia - Divisor