PWC 168 › Home Prime

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.)

Task #2 this week asks us to calculate a so called Home prime. Home primes are found by factoring a number and concatenating the prime factors (including powers, so 20 = 5×2×2), and repeating this until the result is a prime number.

The given example, HP(10) can be found via the following steps: HP(10) = HP(25) = HP(55) = HP(511) = HP(773), and we stop, since 773 is a prime number.

This is a natural problem for recursion:

sub home_prime_recursive {
    my @fac = factor($_[0]);

    @fac == 1 ? $_[0] : home_prime(join '', @fac);
}

I like this solution for its expressiveness, but it’s about 20% slower than the following iterative version:

sub home_prime_iterative {
    my $n = shift;

    while ((my @fac = factor($n)) > 1) {
        $n = join '', @fac;
    }

    return $n;
}

Note that the logic is identical between the two examples; it’s just expressed as a loop conditional and jump versus a conditional and tail call in the preceding example. The difference in performance is down to Perl’s stack and function call overhead. Even using goto &home_prime to manually enforce tail call optimization resulted in zero speedup from the above recursive solution. Language quirks like this don’t matter 90% of the time, but it pays to keep them in the back of your mind for the 10% of cases that need to be optimized.

ch-2.pl full source

Raku

Extremely similar to the recursive Perl version.

use Prime::Factor;

sub home_prime($n) {
    my @fac = prime-factors($n);

    @fac.elems == 1 ?? $n !! home_prime(@fac.join);
}