

 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


use strict;
use warnings;
use feature <say current_sub>;
use experimental 'signatures';
use List::AllUtils <max head uniqint>;
use ntheory <is_square_free is_power euler_phi>;
use Math::AnyNum <:overload idiv iroot ipow is_coprime>;
 
sub table { my $t = shift() * (my $c = 1 + length max @_); ( sprintf( ('%'.$c.'d')x@_, @_) ) =~ s/.{1,$t}\K/\n/gr }
 
sub powerful_numbers ($n, $k = 2) {
    my @powerful;
    sub ($m, $r) {
        $r < $k and push @powerful, $m and return;
        for my $v (1 .. iroot(idiv($n, $m), $r)) {
            if ($r > $k) { next unless is_square_free($v) and is_coprime($m, $v) }
            __SUB__->($m * ipow($v, $r), $r - 1);
        }
    }->(1, 2*$k - 1);
    sort { $a <=> $b } @powerful;
}
 
my(@P, @achilles, %Ahash, @strong);
@P = uniqint @P, powerful_numbers(10**9, $_) for 2..9; shift @P;
!is_power($_) and push @achilles, $_ and $Ahash{$_}++ for @P;
$Ahash{euler_phi $_} and push @strong, $_ for @achilles;
 
say "First 50 Achilles numbers:\n"        . table 10, head 50, @achilles;
say "First 30 strong Achilles numbers:\n" . table 10, head 30, @strong;
say "Number of Achilles numbers with:\n";
for my $l (2..9) {
    my $c; $l == length and $c++ for @achilles;
    say "$l digits: $c";
}