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}·3^{3}and 1800 = 2^{3}·3^{2}·5^{2}.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^{5}·3^{2}. However, 1800 isn’t a Strong Achilles number because: φ(1800) = 480 = 2^{5}·3^{1}·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}φ 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 😉

I’m too old for that. Sorry:)

How much ram do you have? i came up with the exact same idea, but unfortunately my 2gb are running full with that many unsingned long longs. i was storing achilles numbers in a set and the phis in a vector

I used the file-based merge sort mentioned in the most recent entry on the blog. No way it could fit into RAM, I also have 2GB only.