data/problems/302.yml
---
:id: 302
:name: Strong Achilles Numbers
:url: https://projecteuler.net/problem=302
:content: "A positive integer <var>n</var> is **powerful** if p<sup>2</sup> is a divisor
of <var>n</var> for every prime factor p in <var>n</var>.\n\nA positive integer
<var>n</var> is a **perfect power** if <var>n</var> can be expressed as a power
of another positive integer.\n\nA positive integer <var>n</var> is an **Achilles
number** if <var>n</var> is powerful but not a perfect power. For example, 864 and
1800 are Achilles numbers: 864 = 2<sup>5</sup>·3<sup>3</sup> and 1800 = 2<sup>3</sup>·3<sup>2</sup>·5<sup>2</sup>.\n\nWe
shall call a positive integer <var>S</var> a _Strong Achilles number_ if both <var>S</var>
and φ(<var>S</var>) are Achilles numbers.<sup>1</sup> \nFor example, 864 is a Strong
Achilles number: φ(864) = 288 = 2<sup>5</sup>·3<sup>2</sup>. However, 1800 isn't
a Strong Achilles number because: φ(1800) = 480 = 2<sup>5</sup>·3<sup>1</sup>·5<sup>1</sup>.\n\nThere
are 7 Strong Achilles numbers below 10<sup>4</sup> and 656 below 10<sup>8</sup>.\n\nHow
many Strong Achilles numbers are there below 10<sup>18</sup>?\n\n<sup>1</sup> φ
denotes **Euler's totient function**.\n\n"