Detailed mathematical approach

Problem Summary

A strong Achilles number is an integer \(n\) such that both \(n\) and \(\varphi(n)\) are Achilles numbers. An integer is Achilles when it is powerful, but not a perfect power. The problem asks for the number of such \(n\) below \(10^{18}\).

Mathematical Approach

Write

$n=\prod_{i=1}^r p_i^{a_i},\qquad a_i\ge 1.$

1) Achilles condition in exponent language

The number \(n\) is powerful exactly when every exponent is at least \(2\):

$a_i\ge 2\qquad \text{for all }i.$

It is a perfect \(k\)-th power exactly when all exponents are divisible by the same \(k \ge 2\), equivalently when

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

Therefore

$n\text{ is Achilles}\iff a_i\ge 2\ \forall i\quad\text{and}\quad \gcd(a_1,\dots,a_r)=1.$

This turns the first half of the problem into a statement about exponent vectors rather than about the decimal value of \(n\).

2) What the totient contributes

Euler's product formula gives

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

Fix a prime \(q\). Its exponent inside \(\varphi(n)\) is

$v_q(\varphi(n))=\sum_{i=1}^r v_q(p_i-1)+\sum_{\substack{1\le i\le r\\p_i=q}}(a_i-1).$

So every exponent of \(\varphi(n)\) comes from two sources:

1. factors already forced by the numbers \(p_i-1\);

2. the self-contribution \(a_i-1\) when the prime \(q\) itself appears in \(n\).

Thus \(\varphi(n)\) is Achilles exactly when all final values \(v_q(\varphi(n))\) are at least \(2\) and their gcd is \(1\).

3) Worked example: \(n=500\)

Take

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

The exponent vector of \(n\) is \((2,3)\), so \(500\) is powerful and

$\gcd(2,3)=1.$

Hence \(500\) is Achilles.

Now compute the totient:

$\varphi(500)=500\left(1-\frac12\right)\left(1-\frac15\right)=200=2^3\cdot 5^2.$

The exponent vector of \(\varphi(500)\) is \((3,2)\), again all exponents are at least \(2\) and

$\gcd(3,2)=1.$

So \(500\) is a strong Achilles number. This is the smallest example, and it is a good mental model for what the recursion is building.

4) Why the search runs from large primes to small primes

The factorization of \(p-1\) uses only primes strictly smaller than \(p\). Therefore, if the recursion processes prime bases in descending order, then once we move below a prime \(q\), no future decision can increase the exponent of \(q\) inside \(\varphi(n)\).

That means the exponent of \(q\) is now final. The code immediately folds that final exponent into a running gcd for \(\varphi(n)\) and removes \(q\) from the active state. This is the key structural idea that makes the recursion manageable.

5) The meaning of active_factors

The array active_factors is a sorted multiset of prime indices. If the index of a prime \(q\) appears there exactly \(t\) times, then \(t\) is the part of the exponent of \(q\) in \(\varphi(n)\) that has already been created by factors of the form \(p-1\) from larger chosen primes.

Those copies are not finalized yet because the recursion may still decide to include \(q\) itself as a prime factor of \(n\), which would add the extra term \(a_q-1\) to \(v_q(\varphi(n))\).

Alongside that multiset, the code stores two gcd summaries:

$g_n=\gcd(\text{chosen exponents in }n),\qquad g_\varphi=\gcd(\text{already finalized exponents in }\varphi(n)).$

6) Why a brand-new prime must start with exponent \(3\)

Suppose the recursion introduces a prime \(p\) that does not yet occur in active_factors. Then larger primes have contributed no copy of \(p\) to \(\varphi(n)\). The only guaranteed contribution of \(p\) is the self-term \(a-1\) coming from \(p^{a-1}\) in Euler's formula.

To make \(\varphi(n)\) powerful we need

$a-1\ge 2,$

hence

$a\ge 3.$

That is exactly why the code tries deg = 3,4,5,\dots for a genuinely new prime. This also explains the cube-root pruning later on: every fresh prime costs at least \(p^3\).

7) Why an already active prime may start with exponent \(2\)

Now suppose \(p\) already appears in active_factors with multiplicity \(t\ge 1\). Then larger primes have already forced a factor \(p^t\) into \(\varphi(n)\). If we now choose \(p^a\) in \(n\), the final exponent of \(p\) in \(\varphi(n)\) becomes

$t+(a-1).$

The powerful condition is only

$t+(a-1)\ge 2.$

Since \(t\ge 1\), the smallest legal exponent is already \(a=2\). This is why the code has a separate branch where an already active prime is tried with deg = 2,3,4,\dots.

The example \(500=2^2\cdot 5^3\) shows this mechanism clearly: after choosing \(5^3\), the factor \(5-1=4=2^2\) places two copies of the prime \(2\) into active_factors. Then choosing \(2^2\) is enough, because the exponent of \(2\) in \(\varphi(500)\) becomes \(2+(2-1)=3\).

8) When a recursive state is counted

A recursive state already represents a complete candidate \(n\). It is counted exactly when:

$g_n=1,$

every remaining multiplicity inside active_factors is at least \(2\), and

$\gcd\bigl(g_\varphi,\text{all remaining multiplicities}\bigr)=1.$

The meaning is direct:

1. \(g_n=1\) means \(n\) is not a perfect power.

2. Remaining multiplicities at least \(2\) mean \(\varphi(n)\) is powerful.

3. The final gcd equal to \(1\) means \(\varphi(n)\) is not a perfect power.

9) Why the cube-root bound is correct

If we still want to insert a completely new prime \(p\), we must spend at least \(p^3\). Therefore a fresh prime can only be used when

$p^3\le \text{remaining limit}.$

Equivalently,

$p\le \left\lfloor\sqrt[3]{\text{remaining limit}}\right\rfloor.$

This is why the solver computes a cube-root upper bound before opening the “new prime” branch. It removes almost all hopeless candidates very early.

10) Small checkpoints

The implementation contains two explicit tests:

$\text{count}(10^4)=7,\qquad \text{count}(10^8)=656.$

The first seven strong Achilles numbers are

$500,\ 864,\ 1944,\ 2000,\ 2592,\ 3456,\ 5000.$

These checkpoints are important because the full target \(10^{18}\) is far too large for brute force.

How the Code Works

The sieve first generates primes up to a safe bound. Then, for every integer \(m\) in the sieve range, it precomputes the prime factorization of \(m\) as a multiset of prime indices. This lets the recursion merge in the factors of \(p-1\) very cheaply.

The function count_recursive(...) performs three tasks at each state:

1. test whether the current state already forms a strong Achilles number;

2. try primes that already appear in active_factors;

3. try genuinely new primes, subject to the exponent-\(3\) rule and the cube-root bound.

Because the search order is canonical and descending, each valid \(n\) is generated exactly once.

Complexity Analysis

There is no clean closed formula for the running time, because the search tree depends on the arithmetic structure of the numbers \(p-1\). In the worst case the recursion is exponential, but in practice it is kept under control by four strong filters: prime exponents must be large, gcd conditions kill many states, fresh primes satisfy the cube-root bound, and finalized totient exponents are removed from the active state immediately.

The memory usage is modest: recursion depth, a short active multiset, and the sieve/factor tables.

Further Reading

1. Problem page: https://projecteuler.net/problem=302
2. Achilles numbers: https://en.wikipedia.org/wiki/Achilles_number
3. Powerful number: https://en.wikipedia.org/wiki/Powerful_number
4. Perfect power: https://en.wikipedia.org/wiki/Perfect_power
5. Euler totient function: https://en.wikipedia.org/wiki/Euler%27s_totient_function