Detailed mathematical approach

Problem Summary

We need the value of

$\sum_{\substack{1 \le n \lt 10^{10}\\ \varphi(n^2)\text{ is a cube}}} n.$

A direct scan up to \(10^{10}\) would be hopelessly slow, even with a fast totient routine. The key is to describe exactly which prime-exponent patterns make \(\varphi(n^2)\) a perfect cube, and then construct only those \(n\). The numerical Project Euler answer itself is intentionally omitted here.

Mathematical Approach

Write the prime factorization of \(n\) as

$n=\prod_{p} p^{e_p},\qquad e_p\ge 0.$

Only finitely many exponents are nonzero. The entire solution is built around turning the cube condition on \(\varphi(n^2)\) into congruence constraints modulo \(3\).

Totient Formula for a Square

Euler's totient function is multiplicative on coprime arguments, and for prime powers we have

$\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1).$

Applying this to \(n^2=\prod_{p \mid n} p^{2e_p}\) yields

$\varphi(n^2)=\prod_{p \mid n}\varphi\!\left(p^{2e_p}\right)=\prod_{p \mid n} p^{2e_p-1}(p-1).$

Equivalently, since \(\varphi(n)=n\prod_{p \mid n}\left(1-\frac1p\right)\), we also obtain the compact identity

$\varphi(n^2)=n\varphi(n).$

This factorization is what exposes the prime exponents that must be checked modulo \(3\).

Cube Criterion via Prime Valuations

An integer is a perfect cube if and only if every prime exponent in its factorization is divisible by \(3\). Using the \(p\)-adic valuation \(\nu_q(m)\), this becomes

$\nu_q\bigl(\varphi(n^2)\bigr)\equiv 0\pmod 3\qquad\text{for every prime }q.$

From the product formula above, each prime \(q\) receives contributions from two sources:

$\nu_q\bigl(\varphi(n^2)\bigr)=\mathbf{1}_{q\mid n}(2e_q-1)+\sum_{p \mid n}\nu_q(p-1).$

The first term is the exponent contributed by the \(q\)-part of \(n\) itself. The second term records how often \(q\) appears inside the factors \(p-1\) contributed by every chosen prime \(p\).

Why a Descending Prime DFS Works

The code processes primes in descending order. This is crucial because every prime divisor of \(p-1\) is strictly smaller than \(p\). Therefore, once the search reaches a prime \(q\), no later unprocessed prime can create a new \(q\)-contribution through a factor of the form \(p-1\).

So when \(q\) is examined, the residue

$c_q\equiv\sum_{\substack{p \mid n\\ p>q}}\nu_q(p-1)\pmod 3$

is already final. The array residue_mod3 stores exactly these pending residues. This makes the decision at each prime local rather than global, which is why the DFS can prune so aggressively.

Forced and Optional Exponent Classes

Suppose the current residue at prime \(q\) is \(c\in\{0,1,2\}\).

If \(q\) is excluded from \(n\), then its own contribution \(2e_q-1\) does not exist. Since no smaller future prime can add more \(q\)-valuation, exclusion is legal only when \(c=0\).

If \(q\) is included with exponent \(e_q\), then we must satisfy

$c+(2e_q-1)\equiv 0\pmod 3.$

Solving modulo \(3\) gives

$e_q\equiv c+2\pmod 3.$

Hence the minimal admissible exponents are

$c=0 \Rightarrow e_q=2,\qquad c=1 \Rightarrow e_q=3,\qquad c=2 \Rightarrow e_q=1.$

This is exactly the branch structure used in the implementation. Residue \(0\) means the prime is optional; residues \(1\) and \(2\) force inclusion with the smallest matching exponent class.

Worked Example: \(n = 72\)

A small nontrivial valid example is

$72=2^3\cdot 3^2.$

Using the prime-power formula,

$\varphi(72^2)=2^{2\cdot 3-1}(2-1)\cdot 3^{2\cdot 2-1}(3-1)=2^5\cdot 1\cdot 3^3\cdot 2=2^6\cdot 3^3=12^3.$

The residue interpretation is illuminating. Prime \(3\) may start with exponent \(2\) because residue \(0\) requires the class \(e_3\equiv 2\pmod 3\). But \(3-1=2\) contributes one pending factor of \(2\), so when the DFS later reaches prime \(2\) it sees residue \(c=1\). Then

$1+(2e_2-1)\equiv 0\pmod 3\Rightarrow e_2\equiv 0\pmod 3,$

and the minimal choice is \(e_2=3\). This is how the search reconstructs \(72\) from congruence data alone.

Generating Whole Families from a Minimal Base

Once a minimal valid base solution \(n_0\) is fixed, every included prime exponent may be increased by multiples of \(3\):

$n=n_0\prod_{p\in\mathcal{P}} p^{3t_p},\qquad t_p\ge 0.$

This preserves the cube condition because adding \(3\) to an exponent changes \(2e_p-1\) by \(6\), which is \(0\pmod 3\), while the factors \(p-1\) remain unchanged. The program therefore enumerates each minimal base only once, and then sums the entire cube-power family attached to it.

How the Code Works

The solver first builds a smallest-prime-factor sieve up to \(\left\lfloor\sqrt{10^{10}-1}\right\rfloor\). That range is enough for minimal base factors: whenever a new prime is introduced from residue \(0\), its smallest admissible exponent is \(2\), so it must satisfy \(p^2 \lt 10^{10}\).

Next, the code pre-factors every \(p-1\) and stores only the exponents modulo \(3\) in factors_mod3_of_p_minus_1. During DFS, choosing a prime \(p\) simply adds those stored contributions into residue_mod3.

The DFS proceeds from large primes to small primes. At each step it reads the current residue, decides whether the prime is excluded, optional, or forced, multiplies the current base by the smallest valid power, and updates the residue table. A useful prune appears when the residue is \(0\) but even \(p^2\) would exceed the limit: then that prime cannot start a new branch and is skipped deterministically.

When the search reaches the end, it has produced one minimal base solution. The auxiliary recursion multiplier_sum_rec then sums all admissible multipliers \(1,p^3,p^6,\dots\) for the included primes, so the C++, Java, and Python versions all count whole families without rediscovering them one by one.

Complexity Analysis

The preprocessing stage is essentially a sieve plus factorizations of \(p-1\) for primes up to \(\sqrt{L}\), where \(L=10^{10}\). The DFS itself does not have a neat closed-form worst-case bound; in the abstract it is exponential in the number of candidate primes, but in practice the tree is much smaller because residues frequently force a unique decision and the limit cuts off large branches early.

Compared with brute-force totient evaluation for every \(n \lt 10^{10}\), the savings are enormous. Memory usage stays modest: mainly the SPF table, the precomputed factor lists, the residue array, and the recursion stack.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=342
2. Euler's totient function: https://en.wikipedia.org/wiki/Euler%27s_totient_function
3. Multiplicative function: https://en.wikipedia.org/wiki/Multiplicative_function
4. \(p\)-adic valuation: https://en.wikipedia.org/wiki/P-adic_valuation
5. Hardy, G. H.; Wright, E. M. An Introduction to the Theory of Numbers, 6th ed., Oxford University Press. Chapters on multiplicative functions and prime factorization.