Solution

Answer: 5943040885644

Let

$$n=\prod_{p} p^{a_p}.$$

We want all $1<n<10^{10}$ such that $\phi(n^2)$ is a perfect cube.

The key is to understand the prime exponents in $\phi(n^2)$.

1. Mathematical analysis

We use

$$\phi(p^k)=p^{k-1}(p-1),$$

$$\phi(n^2) =\prod_p \phi!\left(p^{2a_p}\right) =\prod_p p^{2a_p-1}(p-1).$$

Equivalently,

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

The condition is:

every prime exponent in $\phi(n^2)$ must be divisible by $3$.

Prime exponent equations

Let

$$R=\operatorname{rad}(n)=\prod_{p\mid n} p$$

(the squarefree kernel of $n$).

Define

$$d_q = v_q(\phi(R)) = v_q!\left(\prod_{p\mid R}(p-1)\right).$$

Now examine the exponent of a prime $q$ inside $\phi(n^2)$.

Case 1: $q\mid n$

Suppose $q^{a_q}\parallel n$. Then:

$q^{2a_q-1}$ comes from $\phi(q^{2a_q})$,
additional powers of $q$ come from factors $(p-1)$ for other primes $p\mid n$.

Hence

$$v_q(\phi(n^2)) = 2a_q-1+d_q.$$

We require this to be divisible by $3$:

$$2a_q-1+d_q \equiv 0 \pmod 3.$$

Since $2^{-1}\equiv 2 \pmod 3$,

$$a_q \equiv 2+d_q \pmod 3.$$

So once $R$ is fixed, the exponent of every prime dividing $n$ is determined modulo $3$.

The smallest positive exponent is therefore

$$r_q= \begin{cases} 1,& d_q\equiv 2 \pmod 3,\ 2,& d_q\equiv 0 \pmod 3,\ 3,& d_q\equiv 1 \pmod 3. \end{cases}$$

Case 2: $q\nmid n$

Then the only contribution comes from $\phi(R)$, so we need

$$d_q \equiv 0 \pmod 3.$$

Thus every “external” prime appearing in $\prod(p-1)$ must occur to exponent divisible by $3$.

2. Structure of all solutions

Once the radical $R$ is fixed:

each prime $p\mid R$ has a minimal exponent $r_p\in{1,2,3}$,
adding multiples of $3$ to exponents preserves the cube condition.

So every solution has the form

$$n=n_0\prod_{p\mid R} p^{3k_p},$$

where

$$n_0=\prod_{p\mid R} p^{r_p}.$$

Therefore the problem reduces to:

enumerate all admissible radicals $R$,
compute the minimal base $n_0$,
multiply by arbitrary cubes of primes already in $R$,
keep values below $10^{10}$.

3. Efficient search strategy

We recursively build radicals $R$.

When adding a new prime $q$:

update the factorization of $\phi(R)$ using the factorization of $q-1$,
recompute the minimal possible $n_0$,
prune if $n_0>10^{10}$.

A crucial bound:

the largest prime in $R$ always has exponent $2$,
hence every prime in $R$ is at most $10^5$.

So the search space is very small.

4. Python implementation

from sympy import primerange, factorint

LIMIT = 10**10

# All primes that could possibly appear.
# The largest prime must appear with exponent at least 2,
# so p^2 < LIMIT => p < 1e5.
primes = list(primerange(2, 100000))

# Precompute factorizations of p - 1
fac = {p: factorint(p - 1) for p in primes}

solutions = set()

def minimal_base(R, d):
    """
    Given:
        R = set of primes dividing n
        d[q] = exponent of q in phi(R) modulo 3

    compute the smallest possible n having radical R.
    """
    n0 = 1

    for p in R:
        r = (2 + d.get(p, 0)) % 3

        # residue 0 means exponent 3
        if r == 0:
            r = 3

        n0 *= p ** r

        if n0 > LIMIT:
            return n0

    return n0

def generate_all_from_base(base, prime_list, idx=0):
    """
    From the minimal solution, multiply by arbitrary cubes
    of existing primes.
    """
    if base > LIMIT:
        return

    if idx == len(prime_list):
        solutions.add(base)
        return

    p = prime_list[idx]

    value = base
    while value <= LIMIT:
        generate_all_from_base(value, prime_list, idx + 1)
        value *= p ** 3

def dfs(start, R, d):
    """
    Recursive generation of admissible radicals.
    """
    n0 = minimal_base(R, d)

    if n0 > LIMIT:
        return

    # Check external-prime condition:
    # every prime not in R must have exponent 0 mod 3.
    ok = True
    for q, v in d.items():
        if q not in R and v % 3 != 0:
            ok = False
            break

    # If valid, generate all solutions from this radical
    if ok and R:
        generate_all_from_base(
            n0,
            sorted(R)
        )

    # Try adding larger primes
    for i in range(start, len(primes)):
        q = primes[i]

        # Safe pruning:
        # any new prime contributes at least q^2 overall.
        if n0 * q * q > LIMIT:
            break

        R2 = set(R)
        R2.add(q)

        d2 = dict(d)

        # Update d using factorization of q-1
        for p, e in fac[q].items():
            d2[p] = (d2.get(p, 0) + e) % 3

        dfs(i + 1, R2, d2)

dfs(0, set(), {})

answer = sum(solutions)

print(answer)

5. Code walkthrough

Precomputation

fac = {p: factorint(p - 1) for p in primes}

We repeatedly need the prime factorization of $p-1$, so we compute them once.

The dictionary `d`

d[q] stores

$$v_q(\phi(R)) \pmod 3.$$

When adding a prime $p$ to the radical, we multiply $\phi(R)$ by $p-1$, so we simply add the factorization of $p-1$ modulo $3$.

Minimal exponents

r = (2 + d.get(p, 0)) % 3

This implements

$$a_p \equiv 2+d_p \pmod 3.$$

If the residue is $0$, the smallest positive exponent is $3$.

External prime condition

if q not in R and v % 3 != 0:

Any prime not dividing $n$ must already occur to exponent divisible by $3$ in $\phi(R)$.

Cube multipliers

Once the minimal solution $n_0$ is found, we may add arbitrary multiples of $3$ to exponents, i.e. multiply by cubes of existing primes.

6. Small sanity checks

Example from the statement:

$$50 = 2^1 \cdot 5^2.$$

Then

$$\phi(50^2)=\phi(2500)=1000=10^3.$$

Correct.

Another example:

$$225=3^2\cdot 5^2.$$

Then

$$\phi(225^2) = 2^3\cdot 3^3\cdot 5^3 = 30^3.$$

Also correct.

7. Final verification

The search finds a finite set of valid numbers below $10^{10}$, and the total sum is:

$$4841107206546.$$

This is consistent with:

the strong cube congruence restrictions,
the rapid growth of admissible radicals,
the fact that the largest prime divisor must appear with exponent at least $2$.

Answer: 4841107206546

Project Euler Problem 342