2018-10-10 18:03:03 -04:00
---
id: 5900f49b1000cf542c50ffad
2021-02-06 04:42:36 +00:00
title: 'Problem 302: Strong Achilles Numbers'
2018-10-10 18:03:03 -04:00
challengeType: 5
2021-02-06 04:42:36 +00:00
forumTopicId: 301956
2021-01-13 03:31:00 +01:00
dashedName: problem-302-strong-achilles-numbers
2018-10-10 18:03:03 -04:00
---
2020-12-16 00:37:30 -07:00
# --description--
2020-02-18 01:40:55 +09:00
2021-02-06 04:42:36 +00:00
A positive integer n is powerful if p2 is a divisor of n for every prime factor p in n.
2020-02-18 01:40:55 +09:00
2021-02-06 04:42:36 +00:00
A positive integer n is a perfect power if n can be expressed as a power of another positive integer.
2020-02-18 01:40:55 +09:00
2021-02-06 04:42:36 +00:00
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 = 25·33 and 1800 = 23·32·52.
2020-02-18 01:40:55 +09:00
2021-02-06 04:42:36 +00:00
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 = 25·32. However, 1800 isn't a Strong Achilles number because: φ(1800) = 480 = 25·31·51.
2020-02-18 01:40:55 +09:00
2021-02-06 04:42:36 +00:00
There are 7 Strong Achilles numbers below 104 and 656 below 108.
2020-02-18 01:40:55 +09:00
2021-02-06 04:42:36 +00:00
How many Strong Achilles numbers are there below 1018?
2020-02-18 01:40:55 +09:00
2021-02-06 04:42:36 +00:00
1 φ denotes Euler's totient function.
2018-10-10 18:03:03 -04:00
2020-12-16 00:37:30 -07:00
# --hints--
2018-10-10 18:03:03 -04:00
2021-02-06 04:42:36 +00:00
`euler302()` should return 1170060.
2018-10-10 18:03:03 -04:00
```js
2020-12-16 00:37:30 -07:00
assert.strictEqual(euler302(), 1170060);
2018-10-10 18:03:03 -04:00
```
2021-01-13 03:31:00 +01:00
# --seed--
## --seed-contents--
```js
function euler302() {
return true;
}
euler302();
```
2020-12-16 00:37:30 -07:00
# --solutions--
2020-08-13 17:24:35 +02:00
2021-01-13 03:31:00 +01:00
```js
// solution required
```