Detailed mathematical approach

Problem Summary

For a given bound \(n\), we count distinct real values of

$\sqrt{x+\sqrt y+\sqrt z},\qquad 0 \lt x \le n,$

where \(y\) and \(z\) are non-squares and the outer radical can be denested into a finite signed sum of simple square roots. Different triples \((x,y,z)\) may represent the same real number, but that value must be counted only once. The implementations evaluate this count at \(n=5{,}000{,}000\).

The program organizes the denestable values into two structural families. The first family comes from denestings with two simple roots. The second family comes from denestings with four simple roots and one minus sign. The final formula counts both families and then removes the four-root cases that collapse back to a value already counted in the two-root family.

Mathematical Approach

Let \(F(n)\) denote the number of distinct denestable values with integer part \(x\le n\). The implementation builds \(F(n)\) from an arithmetic kernel \(f(s)\) and three counting terms \(C_1(n)\), \(C_2^{\mathrm{ord}}(n)\), and \(C_3(n)\).

Step 1: Primitive Two-Root Denestings

Start with a value of the form

$V=\sqrt{k\alpha}+\sqrt{k\beta},\qquad \alpha \gt \beta \ge 1,\qquad \gcd(\alpha,\beta)=1,\qquad k\ge 1.$

Squaring gives

$V^2=k(\alpha+\beta)+2k\sqrt{\alpha\beta}.$

If \(\alpha\beta\) is not a square, then \(V^2\) has exactly one irrational square-root direction, and it fits the required pattern because

$2k\sqrt{\alpha\beta}=\sqrt{k^2\alpha\beta}+\sqrt{k^2\alpha\beta},$

with \(k^2\alpha\beta\) still non-square. So each primitive pair \((\alpha,\beta)\) produces one infinite scaling family of admissible values, and the integer part is

$x=k(\alpha+\beta).$

For a fixed primitive sum

$s=\alpha+\beta,$

the scale \(k\) can be chosen in exactly

$\left\lfloor\frac{n}{s}\right\rfloor$

ways.

Step 2: Count the Primitive Kernels \(f(s)\)

For fixed \(s\ge 3\), how many primitive pairs \((\alpha,\beta)\) with \(\alpha+\beta=s\) belong to the first family?

The number of coprime decompositions \(s=\alpha+\beta\) with \(\alpha \gt \beta \ge 1\) is

$\frac{\varphi(s)}{2},$

because each reduced residue class modulo \(s\) corresponds to one ordered coprime split, and dividing by \(2\) forgets the order.

Now remove the bad cases where \(\alpha\beta\) is a square. Since \(\gcd(\alpha,\beta)=1\), this happens exactly when

$\alpha=u^2,\qquad \beta=v^2,\qquad \gcd(u,v)=1.$

So the excluded pairs are precisely the primitive representations

$s=u^2+v^2,\qquad u \gt v \ge 1,\qquad \gcd(u,v)=1.$

If \(R(s)\) denotes the number of those primitive two-square representations, then the kernel used by the implementations is

$f(s)=\frac{\varphi(s)}{2}-R(s).$

Therefore the total contribution of the two-root family is

$C_1(n)=\sum_{s\le n} f(s)\left\lfloor\frac{n}{s}\right\rfloor.$

Step 3: A Genuine Four-Root Family

The second family combines two primitive kernels. Take two primitive pairs \((\alpha,\beta)\) and \((\gamma,\delta)\), each counted by \(f\), and form

$W=\sqrt{k\alpha\gamma}+\sqrt{k\alpha\delta}+\sqrt{k\beta\gamma}-\sqrt{k\beta\delta}.$

Expanding \(W^2\) gives a crucial cancellation:

$W^2=k(\alpha+\beta)(\gamma+\delta)+2k(\alpha-\beta)\sqrt{\gamma\delta}+2k(\gamma-\delta)\sqrt{\alpha\beta}.$

The mixed term involving \(\sqrt{\alpha\beta\gamma\delta}\) disappears because of the sign pattern. This leaves exactly two square-root directions, so \(W\) is another denesting of the required form.

If we write

$s=\alpha+\beta,\qquad t=\gamma+\delta,$

then the integer part of \(W^2\) is

$x=kst.$

Hence each ordered pair of primitive kernels \((s,t)\) contributes

$\left\lfloor\frac{n}{st}\right\rfloor$

scaled values, and the ordered count is

$C_2^{\mathrm{ord}}(n)=\sum_{s\le n}\sum_{t\le n} f(s)f(t)\left\lfloor\frac{n}{st}\right\rfloor.$

The superscript “ord” matters: swapping the two kernels does not change the final value, so this sum counts the generic four-root construction twice.

Step 4: Detect the Four-Root Values that Collapse to Two Roots

Not every ordered four-root construction is genuinely new. Some of them collapse to only two independent squarefree radicals and are therefore already included in \(C_1(n)\).

Write the two primitive pairs as

$\alpha=\sigma_1 a^2,\qquad \beta=\sigma_2 b^2,\qquad \gamma=\tau_1 c^2,\qquad \delta=\tau_2 d^2,$

where \(\sigma_1,\sigma_2,\tau_1,\tau_2\) are squarefree. The four radicals inside \(W\) then have squarefree parts

$\sigma_1\tau_1,\qquad \sigma_1\tau_2,\qquad \sigma_2\tau_1,\qquad \sigma_2\tau_2.$

A collision with the two-root family occurs exactly when these four squarefree products merge into only two distinct squarefree directions. The implementation parameterizes those collisions by squarefree, pairwise-coprime factors \(\rho_1,\rho_2,\rho_3,\rho_4\) such that

$\sigma_1=\rho_1\rho_2,\qquad \sigma_2=\rho_3\rho_4,\qquad \tau_1=\rho_1\rho_3,\qquad \tau_2=\rho_2\rho_4.$

Then

$\sqrt{\sigma_1\tau_1}=\rho_1\sqrt{\rho_2\rho_3},\qquad \sqrt{\sigma_2\tau_2}=\rho_4\sqrt{\rho_2\rho_3},$

and likewise

$\sqrt{\sigma_1\tau_2}=\rho_2\sqrt{\rho_1\rho_4},\qquad \sqrt{\sigma_2\tau_1}=\rho_3\sqrt{\rho_1\rho_4}.$

So the supposed four-root expression is really a two-root value. Let \(C_3(n)\) be the number of ordered constructions of exactly this collapsing kind. These must be removed from the ordered four-root count before the final symmetry factor is applied.

Step 5: Final Formula

After subtracting the collapsing ordered constructions and then forgetting the order of the two primitive kernels, the implementations compute

$\boxed{F(n)=C_1(n)+\frac{C_2^{\mathrm{ord}}(n)-C_3(n)}{2}.}$

This is the exact decomposition used by the C++, Python, and Java implementations.

Worked Example

A simple two-root example is

$V=\sqrt5+\sqrt2.$

Then

$V^2=7+2\sqrt{10}=7+\sqrt{10}+\sqrt{10}.$

Here the primitive kernel is \(s=5+2=7\), and because \(5\cdot2=10\) is not a square, this value belongs to the first family. Every scale \(k\) with \(7k\le n\) gives another valid value from the same kernel.

A genuine four-root example uses \((\alpha,\beta)=(2,1)\) and \((\gamma,\delta)=(3,1)\):

$W=\sqrt6+\sqrt2+\sqrt3-1.$

Its square is

$W^2=(2+1)(3+1)+2(2-1)\sqrt3+2(3-1)\sqrt2=12+2\sqrt3+4\sqrt2.$

So the integer part is \(12=3\cdot4\), which shows why the second family is indexed by products of primitive kernel sums.

How the Code Works

The implementations first build a totient sieve up to \(n\). From that array they initialize

$f(s)=\frac{\varphi(s)}{2}$

for \(s\ge 3\), then subtract one for every primitive representation \(s=u^2+v^2\) with \(u \gt v\) and \(\gcd(u,v)=1\). That produces the kernel sequence \(f(s)\).

Next they form prefix sums of \(f\). The first family \(C_1(n)\) is then a direct divisor-style sum. The ordered second-family term \(C_2^{\mathrm{ord}}(n)\) is not evaluated by a quadratic double loop. Instead, the code groups equal quotients of \(\left\lfloor n/i\right\rfloor\) into harmonic intervals and combines them with prefix sums, which turns the convolution into a much smaller collection of block sums.

The overlap term \(C_3(n)\) is handled separately. The code precomputes squarefree flags, coprimality lookup tables, and squares up to \(\lfloor\sqrt n\rfloor\). It then enumerates only the parameter combinations that can force a four-root value to collapse into two squarefree directions, using many early inequality breaks to prune the search. The C++ implementation parallelizes this expensive overlap phase; the Python version mirrors the same mathematics more directly, and the Java version reuses the same optimized core computation.

Complexity Analysis

Building the totient sieve and the kernel \(f\) takes \(O(n\log\log n)\) time and \(O(n)\) memory. The first family sum \(C_1(n)\) is \(O(n)\). The ordered convolution \(C_2^{\mathrm{ord}}(n)\) is accelerated by harmonic blocking and prefix sums, so the code avoids the naive \(O(n^2)\) double loop and works with a subquadratic number of quotient blocks instead.

The practical bottleneck is the overlap correction \(C_3(n)\). Its exact worst-case count is awkward to state cleanly because it depends on several nested squarefree and coprimality constraints, but the implementation reduces it sharply through precomputed tables, squarefree filtering, and early stopping inequalities. Overall memory usage remains \(O(n)\), dominated by the arithmetic arrays up to \(n\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=585
2. Nested radical: Wikipedia - Nested radical
3. Euler's totient function: Wikipedia - Euler's totient function
4. Coprime integers: Wikipedia - Coprime integers
5. Sum of two squares: Wikipedia - Sum of two squares
6. Square-free integer: Wikipedia - Square-free integer