user
|  |
| --- |
| This page uses content from **Wikipedia**. The original article was at Achilles number. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |

An **Achilles number** is a number that is powerful but imperfect. *Named after Achilles, a hero of the Trojan war, who was also powerful but imperfect.*

A positive integer **n** is a powerful number if, for every prime factor **p** of **n**, **p2** is also a divisor.

In other words, every prime factor appears at least squared in the factorization.

All **Achilles numbers** are powerful. However, not all powerful numbers are **Achilles numbers**: only those that cannot be represented as **mk**, where **m** and **k** are positive integers greater than **1**.

A ***strong* Achilles number** is an **Achilles number** whose **Euler totient (𝜑)** is also an **Achilles number**.

E.G.

**108** is a powerful number. Its prime factorization is **22 × 33**, and thus its prime factors are **2** and **3**. Both **22 = 4** and **32 = 9** are divisors of **108**. However, **108** cannot be represented as **mk**, where **m** and **k** are positive integers greater than **1**, so **108** is an **Achilles number**.

**360** is *not* an **Achilles number** because it is not powerful. One of its prime factors is **5** but **360** is not divisible by **52 = 25**.

Finally, **784** is *not* an **Achilles number**. It is a powerful number, because not only are **2** and **7** its only prime factors, but also **22 = 4** and **72 = 49** are divisors of it. Nonetheless, it is a perfect power; its square root is an even integer, so it is *not* an **Achilles number**.

**500 = 22 × 53** is a ***strong* Achilles number** as its Euler totient, **𝜑(500)**, is **200 = 23 × 52** which is *also* an **Achilles number**.

Task

* Find and show the first 50 **Achilles numbers**.
* Find and show at least the first 20 ***strong* Achilles numbers**.
* For at least 2 through 5, show the count of **Achilles numbers** with that many digits.

See also

* Wikipedia: Achilles number * OEIS:A052486 - Achilles numbers - powerful but imperfect numbers * OEIS:A194085 - Strong Achilles numbers: Achilles numbers m such that phi(m) is also an Achilles number * Related task: Powerful numbers * Related task: Totient function
assistant
Timing is going to be system / OS dependent.

```
use Prime::Factor;
use Math::Root;

sub is-square-free (Int \n) {
    constant @p = ^100 .map: { next unless .is-prime; .² };
    for @p -> \p { return False if n %% p }
    True
}

sub powerful (\n, \k = 2) {
    my @p;
    p(1, 2*k - 1);
    sub p (\m, \r) {
        @p.push(m) and return if r < k;
        for 1 .. (n / m).&root(r) -> \v {
            if r > k {
                next unless is-square-free(v);
                next unless m gcd v == 1;
            }
            p(m * v ** r, r - 1)
        }
    }
    @p
}

my $achilles = powerful(10**9).hyper(:500batch).grep( {
    my $f = .&prime-factors.Bag;
    (+$f.keys > 1) && (1 == [gcd] $f.values) && (.sqrt.Int² !== $_)
} ).classify: { .chars }

my \𝜑 = 0, |(1..*).hyper.map: -> \t { t × [×] t.&prime-factors.squish.map: { 1 - 1/$_ } }

my %as = Set.new: flat $achilles.values».list;

my $strong = lazy (flat $achilles.sort».value».list».sort).grep: { ?%as{𝜑[$_]} };

put "First 50 Achilles numbers:";
put (flat $achilles.sort».value».list».sort)[^50].batch(10)».fmt("%4d").join("\n");

put "\nFirst 30 strong Achilles numbers:";
put   $strong[^30].batch(10)».fmt("%5d").join("\n");

put "\nNumber of Achilles numbers with:";
say "$_ digits: " ~ +$achilles{$_} // 0 for 2..9;

printf "\n%.1f total elapsed seconds\n", now - INIT now;

```

Output:

```
First 50 Achilles numbers:
  72  108  200  288  392  432  500  648  675  800
 864  968  972 1125 1152 1323 1352 1372 1568 1800
1944 2000 2312 2592 2700 2888 3087 3200 3267 3456
3528 3872 3888 4000 4232 4500 4563 4608 5000 5292
5324 5400 5408 5488 6075 6125 6272 6728 6912 7200

First 30 strong Achilles numbers:
  500   864  1944  2000  2592  3456  5000 10125 10368 12348
12500 16875 19652 19773 30375 31104 32000 33275 37044 40500
49392 50000 52488 55296 61731 64827 67500 69984 78608 80000

Number of Achilles numbers with:
2 digits: 1
3 digits: 12
4 digits: 47
5 digits: 192
6 digits: 664
7 digits: 2242
8 digits: 7395
9 digits: 24008

6.1 total elapsed seconds
```

Could go further but slows to a crawl and starts chewing up memory in short order.

```
10 digits: 77330
11 digits: 247449
12 digits: 788855

410.4 total elapsed seconds

```