Search Problems   RSS Feed
projecteuler.net

Strong Achilles Numbers

 Published on Saturday, 18th September 2010, 07:00 pm; Solved by 797;
Difficulty rating: 60%

Problem 302

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.