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

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

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

натуральное n является ахиллесовым числом, если n полностепенное, но не является совершенной степенью. Например, 864 и 1800 - ахиллесовы числа: 864 = 25·33, и 1800 = 23·32·52.

Назовем натуральное S сильным ахиллесовым числом, если и S, и φ(S) являются ахиллесовыми числами.1
Например, 864 - сильное Ахиллесово число: φ(864) = 288 = 25·32. Однако, 1800 не является сильным ахиллесовым числом, т. к. φ(1800) = 480 = 25·31·51.

Существует 7 сильных ахиллесовых чисел менее 104, и 656 менее 108.

Сколько существует сильных ахиллесовых чисел менее 1018?

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

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