Задача 302
Сильные ахиллесовы числа

Положительное целое n называется полностепенным (powerful), если p^(2) является делителем n, для каждого простого множителя p, содержащегося в n.

Положительное целое n является совершенной степенью, если n можно представить как степень другого положительного целого.

Положительное целое n является ахиллесовым числом, если n полностепенное, но не является совершенной степенью. Например, 864 и 1800 - ахиллесовы числа: 864 = 2^(5)·3^(3), и 1800 = 2^(3)·3^(2)·5^(2).

Назовём положительное целое S сильным ахиллесовым числом, если и S, и φ(S) являются ахиллесовыми числами.^(1)
Например, 864 - сильное Ахиллесово число: φ(864) = 288 = 2^(5)·3^(2). Однако, 1800 не является сильным ахиллесовым числом, т. к. φ(1800) = 480 = 2^(5)·3^(1)·5^(1).

Существует 7 сильных ахиллесовых чисел менее 10^(4), и 656 менее 10^(8).

Сколько существует сильных ахиллесовых чисел менее 10^(18)?

^(1) φ обозначает функцию Эйлера (Euler's totient function).

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net