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 $limit by 10 every time through outer loop.

The sieve operations give me an array of @composite numbers from [2,$lim). Getting the prime @factors from that is a simple grep to invert the results.

Finally, there’s a simple O(n²) search through the prime factors to generate the list of brilliant numbers. This already does not generate any duplicates, so n² 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 = 2⁴ * 3². gcd(4,2) = 2. Thus 144 is a perfect square (12²), 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 = 2² * 3¹ 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 maps 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.