Detailed mathematical approach

Problem Summary

The implementations compute a modular quantity \(H(N)\) for \(N=10^{15}\), with modulus

$M=1031^3+2.$

Instead of scanning all integer pairs \((x,y)\) with \(\max(|x|,|y|)\le N\), the solution starts from the algebraic classification used for the nested-radical identities behind the problem. Once that classification is available, the task becomes:

$H(N)=\sum_{\substack{(x,y)\ \text{admissible}\\ \max(|x|,|y|)\le N}} (|x|+|y|)\pmod{M}.$

The key point is that every admissible pair comes from a primitive parameter pair together with a square scaling factor, so the search can be reorganized arithmetically rather than geometrically.

Mathematical Approach

The implementations use two primitive families, depending on the parity of one parameter. To avoid exposing code symbols, let the coprime parameters be \(a,b\in \mathbb{Z}_{>0}\) with \(a\ne 2b\), and let the common scale be \(t\ge 1\).

Step 1: Primitive Parameterization

When \(b\) is odd, the primitive pair is

$X_{\mathrm{odd}}=b(b+4a)^3,\qquad Y_{\mathrm{odd}}=4a(a-2b)^3.$

When \(b\) is even, the primitive pair is

$X_{\mathrm{even}}=2b\left(\frac{b}{2}+2a\right)^3,\qquad Y_{\mathrm{even}}=a(a-2b)^3.$

These two branches are exactly the two branches used by the C++, Python, and Java implementations. The coprimality condition

$\gcd(a,b)=1$

eliminates redundant representations, and the excluded line

$a=2b$

is the degenerate case where one cubic factor vanishes.

Step 2: Square Scaling Generates the Full Family

Each primitive pair produces an infinite family by multiplying both coordinates by a common square:

$ (x,y)=\left(t^2X_\ast,\ t^2Y_\ast\right), $

where \((X_\ast,Y_\ast)\) means the appropriate primitive pair from the odd or even branch.

Therefore, for a fixed primitive seed, the admissible values under the box constraint are determined by

$t^2\max(|X_\ast|,|Y_\ast|)\le N,$

so the largest allowed scale is

$t_{\max}=\left\lfloor \sqrt{\frac{N}{\max(|X_\ast|,|Y_\ast|)}} \right\rfloor.$

This is why the outer arithmetic work is done only on primitive seeds; all non-primitive solutions are absorbed into a single closed-form sum over \(t\).

Step 3: Cube-Free Kernels Remove the Collapsing Cases

The implementations precompute the cube-free kernel

$\operatorname{cf}(n)=\prod_{p} p^{v_p(n)\bmod 3},$

meaning that every full cube \(p^3\) is stripped away, while exponents \(1\) and \(2\) remain. The primitive pair is kept only if the two relevant kernels differ.

For odd \(b\), the required inequality is

$\operatorname{cf}(b)\ne \operatorname{cf}(4a).$

For even \(b\), the required inequality is

$\operatorname{cf}(2b)\ne \operatorname{cf}(a).$

This filter removes the cases where the two cube-root components collapse to the same cube-free part and the intended nested-radical structure is lost.

Step 4: Sum All Square Multiples at Once

For one primitive seed, every scaled pair contributes

$|t^2X_\ast|+|t^2Y_\ast|=t^2\bigl(|X_\ast|+|Y_\ast|\bigr).$

Hence the total contribution of that seed is

$\bigl(|X_\ast|+|Y_\ast|\bigr)\sum_{t=1}^{t_{\max}} t^2.$

The implementations use the standard closed form

$\sum_{t=1}^{u} t^2=\frac{u(u+1)(2u+1)}{6},$

so the whole scaled family is compressed into one arithmetic term rather than one loop over each individual pair.

Step 5: Root Bounds Make the Search Finite

The fourth-root bound for the outer parameter comes from the fact that the positive coordinate in each branch already grows like \(b^4\). In particular, the formulas imply

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

Once \(b\) is fixed, the positive coordinate alone gives an upper bound for \(a\). For odd \(b\),

$b(b+4a)^3\le N \quad\Longrightarrow\quad a\le \frac{\left\lfloor (N/b)^{1/3}\right\rfloor-b}{4}.$

For even \(b\),

$2b\left(\frac{b}{2}+2a\right)^3\le N \quad\Longrightarrow\quad a\le \frac{\left\lfloor (N/(2b))^{1/3}\right\rfloor-\frac{b}{2}}{2}.$

These cube-root bounds drastically reduce the search space before the remaining filters are applied.

Worked Example: \(H(1000)=2535\)

The implementations include a small checkpoint at \(N=1000\). Here

$\left\lfloor(4N)^{1/4}\right\rfloor=\left\lfloor 4000^{1/4}\right\rfloor=7.$

Only two primitive seeds survive all conditions and still satisfy the size bound.

First, with \(a=1\) and odd \(b=1\),

$X_\ast=1(1+4)^3=125,\qquad Y_\ast=4\cdot 1\cdot(1-2)^3=-4.$

The kernel condition is \( \operatorname{cf}(1)\ne \operatorname{cf}(4)\), so the seed is valid. Its scale limit is

$t_{\max}=\left\lfloor\sqrt{\frac{1000}{125}}\right\rfloor=2,$

so its total contribution is

$ (125+4)(1^2+2^2)=129\cdot 5=645. $

Second, with \(a=1\) and even \(b=2\),

$X_\ast=2\cdot 2\left(1+2\right)^3=108,\qquad Y_\ast=1(1-4)^3=-27.$

Now \( \operatorname{cf}(4)\ne \operatorname{cf}(1)\), and

$t_{\max}=\left\lfloor\sqrt{\frac{1000}{108}}\right\rfloor=3.$

This contributes

$ (108+27)(1^2+2^2+3^2)=135\cdot 14=1890. $

Adding the two surviving families gives

$645+1890=2535,$

which matches the checkpoint in the implementations exactly.

How the Code Works

The implementation begins by computing exact integer fourth roots, cube roots, and square roots, so the search bounds are numerically safe even at very large \(N\).

It then builds a smallest-prime-factor sieve up to the limit needed for all cube-free-kernel lookups. From that sieve it derives the table of cube-free kernels \( \operatorname{cf}(n)\).

Next, it scans the outer parameter up to \( \lfloor(4N)^{1/4}\rfloor\). Odd values use the odd primitive formula; even values use the even primitive formula. For each branch it computes the cube-root upper bound for the inner parameter, then applies, in order, the coprimality test, the excluded diagonal test, the cube-free-kernel inequality, and the final max-norm check.

Whenever a primitive seed survives, the implementation computes \(t_{\max}\), evaluates the closed form for \(1^2+\cdots+t_{\max}^2\), multiplies by \(|X_\ast|+|Y_\ast|\), and adds the result modulo \(M\).

The C++ version parallelizes the outer-parameter loop across several threads, while the Python and Java implementations perform the same arithmetic sequentially. In all three languages, the mathematical work is the same.

Complexity Analysis

Let \(B=\lfloor(4N)^{1/4}\rfloor\). The outer loop runs over \(O(B)=O(N^{1/4})\) values.

For a fixed outer parameter \(b\), the inner limit is \(O((N/b)^{1/3})\). Summing this over all \(b\le B\) gives the rough bound

$\sum_{b\le B} O\!\left((N/b)^{1/3}\right)=O\!\left(N^{1/3}\sum_{b\le B} b^{-1/3}\right)=O(N^{1/2}).$

So the arithmetic enumeration is about \(O(N^{1/2})\) candidate checks before constant-factor pruning from coprimality and kernel filters. The sieve for cube-free kernels reaches only the largest parameter size, which is \(O(N^{1/3})\), so its cost is \(O(N^{1/3}\log\log N)\) time and \(O(N^{1/3})\) memory.

In practice, the wall-clock time is better than a naive pair scan by many orders of magnitude, and the threaded C++ implementation further reduces elapsed time without changing the asymptotic count.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=880
2. Nested radicals: Wikipedia — Nested radical
3. p-adic valuation: Wikipedia — p-adic valuation
4. Power-free integers and cube-free structure: Wikipedia — Power-free integer
5. Sum of squares: Wikipedia — Square pyramidal number