Project Euler #302

A positive integer n is powerful if p² 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⁵·3³ and 1800 = 2³·3²·5².

We shall call a positive integer S a Strong Achilles number if both S and φ(S) are Achilles numbers.1
For example, 864 is a Strong Achilles number: φ(864) = 288 = 2⁵·3². However, 1800 isn’t a Strong Achilles number because: φ(1800) = 480 = 2⁵·3¹·5¹.

There are 7 Strong Achilles numbers below 10⁴ and 656 below 10⁸.

How many Strong Achilles numbers are there below 10¹⁸?

¹ φ denotes Euler’s totient function.

Huh, it’s the first time I made it into top 100 fastest solvers. I would have been in the top 50 because I had it all figured out just like the rest of Eulerians and then… (however hard to believe because I considered myself a better coder than mathematician 😉 )… then I must have messed something up in the implementation because I kept getting incorrect results. Finally I semi-brute forced it by generating all Achilles numbers and their corresponding phi values and then reiterated over the set of phi’s checking if they are in the set of Achilles numbers. It took about an hour to compute :/ I hope I’ll do better next time 😉