Strong Achilles Numbers

A positive integer $n$ is powerful if $p^2$ is a divisor of $n$ for every prime factor $p$ in $n$.

A positive integer $n$ is a perfect power if $n$ can be expressed as a power of another positive integer.

A positive integer $n$ is an Achilles number if $n$ is powerful but not a perfect power. For example, $864$ and $1800$ are Achilles numbers: $864 = 2^5 \cdot 3^3$ and $1800 = 2^3 \cdot 3^2 \cdot 5^2$.

We shall call a positive integer $S$ a Strong Achilles number if both $S$ and $\phi(S)$ are Achilles numbers.1
For example, $864$ is a Strong Achilles number: $\phi(864) = 288 = 2^5 \cdot 3^2$. However, $1800$ isn’t a Strong Achilles number because: $\phi(1800) = 480 = 2^5 \cdot 3^1 \cdot 5^1$.

There are $7$ Strong Achilles numbers below $10^4$ and $656$ below $10^8$.

How many Strong Achilles numbers are there below $10^{18}$?

1 $\phi$ denotes Euler’s totient function.

This is a complex number theory problem that requires significant computation and application of established methods and theorems to solve. Here is a general approach on how you could tackle such a problem:

1. **Achilles Numbers**: An Achilles number is powerful but not a perfect power. An integer $n = p_1^{a_1}p_2^{a_2} … p_k^{a_k}$ is a perfect power iff $gcd(a_1, a_2, …, a_k) > 1$. Therefore, to generate all powerful numbers up to a limit $N$, we should first generate the prime powers up to $\sqrt{N}$, multiply them in all ways countably less than $N$, and finally remove perfect powers.

2. **Strong Achilles Numbers**: For $n = p_1^{a_1}p_2^{a_2} … p_k^{a_k}$, you could calculate $\phi(n) = (p_1-1)p_1^{a1-1}(p_2-1)p_2^{a2-1} … (p_k-1)p_k^{ak-1}$, but a simpler approach is to observe that $phi(n)$ is always a powerful number. This is because $phi(n)$ swaps each $p_i$ with $p_i-1$, which must also be a square if $p_i$ was a square. Therefore a Strong Achilles number is just an Achilles number where the exponents forming the number are powerful numbers themselves.

3. **Computational Approach**: To generate all powerful exponents up to $N$, first calculate all primes up to $\sqrt{N}$. Then calculate every square of a prime and every cube of a prime. Combine these in various ways to produce the powerful exponents. It’s similar to the knapsack problem. You could then use these exponents to generate the Strong Achilles numbers.

4. **Optimization**: Since the problem asks for numbers below $10^{18}$, straightforward computation would be highly inefficient and infeasible. You would need clever optimization methods, data structures and probably algorithms for fast generation of primes and prime factorization for this. It involves highly nontrivial computation and analysis.

In fact, this problem is similar to Project Euler Problem 302, a deeply challenging problem designed for advanced mathematicians and programmers.

Due to the high complexity and computational nature of the solution to this problem, the exact count of Strong Achilles numbers under $10^{18}$ is not readily produced. This problem is probably better approached with rigorous computational software and high-performance computing methods.

More Answers: