# PWC 169 › Brilliant and Achilles Numbers

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

This week, both tasks are quite short, so I’ll combine them into a single blog post.

## Task 1 › Brilliant Numbers

Brilliant numbers are composite numbers with exactly two prime factors. Additionally, the prime factors must be the same length.

My complete code is as follows:

```sub brilliant {
my \$count = \$_[0];

my @comp = (undef, 1, undef); # Composite numbers
my @brilliant;                # Results

for (my \$lim = 10; \$count > 0; \$lim .= '0') {
# Partial sieve
for my \$n (2..\$lim) {
next if \$n > 2 and \$comp[\$n];
\$comp[\$_] = \$_ for map { \$n * \$_ } 2..\$lim/\$n;
}

# Pull out prime factors between \$lim/10 and \$lim
my @fac = grep { !\$comp[\$_] } (\$lim/10)..\$lim;

# Map all unique 2-permutations of prime factors \$lim/10..\$lim
while (my (\$i1, \$n1) = each @fac) {
push @brilliant, \$n1 * \$_ for @fac[\$i1..\$#fac];
\$count -= @fac - \$i1;
}
}

(sort { \$a <=> \$b } @brilliant)[0..\$_[0]-1]
}
```

My solution begins with a modified Sieve of Eratosthenes. Since we don’t know when we’re going to stop, I loop over the factor length by multiplying the upper `\$lim`it by 10 every time through outer loop.

The sieve operations give me an array of `@comp`osite numbers from [2,`\$lim`). Getting the prime `@fac`tors from that is a simple `grep` to invert the results.

Finally, there’s a simple O(n2) search through the prime factors to generate the list of brilliant numbers. This already does not generate any duplicates, so n2 is the best we can do for this step.

## Task 2 › Achilles Numbers

Achilles numbers are both powerful but not a perfect power. Meaning, every prime factor appears at least twice, and the number itself is not a perfect square, cube, or higher integer power.

If the exponents of each prime factor are in an array called `@exp`, this second check can be expressed very succinctly as `gcd(@exp) == 1`, since if the exponents are not in reduced form, this greatest common divisor would be the perfect power of the number. For example, 144 = 24 * 32. gcd(4,2) = 2. Thus 144 is a perfect square (122), and would not be an Achilles number.

I will use `List::Util`, which is a core module, and `Math::Prime::Util`, which is not. However, I think we all know how to factor numbers by now!

```use Math::Prime::Util qw< gcd factor_exp >;
use List::Util qw< all any >;

sub achilles {
map  { \$_->[0] }
grep { all { \$_ > 1 } @{\$_->[1]} and gcd(@{\$_->[1]}) == 1 }
map  { [ \$_ => [ map { \$_->[1] } factor_exp(\$_) ] ] } 2..\$_[0];
}
```

Reading from the bottom up, we loop over the entire number range specified (`2..\$_[0]`), and `map` that to an array ref of the number itself, and an array of the exponents of each prime factor of that number. We throw away the prime factors themselves, as they are not needed.

For example, the number 12 = 22 * 31 would look like:

```[12 => [2,1]]
```

The next line up (`grep { ... }`) then performs two checks:

1. `all` exponents are greater than 1, and
2. the `gcd` of all exponents is equal to 1

If those checks pass, the next line up `map`s the array ref back to the number itself, which will be part of the function’s return.

This is a fairly idiomatic type of transformation in Perl.