Project Euler Problem 302

Project Euler Problem 302

Solution

Answer: 1170060

Let

$$n=\prod_{i=1}^k p_i^{a_i}.$$

A number is powerful iff every exponent satisfies $a_i\ge 2$.

A number is a perfect power iff

$$\gcd(a_1,a_2,\dots,a_k)\ge 2.$$

Therefore:

$$n \text{ is Achilles } \iff \left(a_i\ge2\ \forall i\right) \text{ and } \gcd(a_1,\dots,a_k)=1.$$

For Euler’s totient,

$$\phi(n)=\prod_{i=1}^k p_i^{a_i-1}(p_i-1).$$

So the prime exponents in $\phi(n)$ come from two sources:

1. the $a_i-1$ terms;
2. the factorisations of $p_i-1$.

The search can therefore be performed recursively over exponent patterns and compatible prime chains, while maintaining:

• $n<10^{18}$,
• all exponents in $n$ at least $2$,
• $\gcd(\text{exponents of }n)=1$,
• every prime exponent in $\phi(n)\ge2$,
• $\gcd(\text{exponents of }\phi(n))=1$.

The recursion is heavily pruned because:

• only small exponent vectors are possible below $10^{18}$,
• each added prime rapidly increases the value,
• factorisations of $p-1$ tightly constrain admissible primes.

A correct implementation reproduces the checks given in the problem statement:

• below $10^4$: $7$,
• below $10^8$: $656$.

The full computation for $10^{18}$ yields:

$$1170060$$

This matches published verified Project Euler solution lists.

Answer: 1170060