RabbitFarm

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

Calculate the first 13 Perrin Primes.

Solution

use strict;
use warnings;
use boolean;
use Math::Primality qw/is_prime/;

sub n_perrin_prime_r{
    my($n, $perrins, $perrin_primes) = @_;
    return $perrin_primes if keys %{$perrin_primes} == $n;
    my $perrin = $perrins->[@{$perrins} - 3] + $perrins->[@{$perrins} - 2];
    push @{$perrins}, $perrin;
    $perrin_primes->{$perrin} = -1 if is_prime($perrin);
    n_perrin_prime_r($n, $perrins, $perrin_primes);
}

sub perrin_primes{
    return n_perrin_prime_r(13, [3, 0, 2], {});
}

MAIN:{
    print join(", ", sort {$a <=> $b} keys %{perrin_primes()}) . "\n";
}

Sample Run

$ perl perl/ch-1.pl
2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977

Notes

The solution here incorporated a lot of elements from previous weekly challenges. That is to say it is quite familiar, we recursively generate the sequence which is stored as hash keys and, once completed, sort and print the results. The hash keys are a convenient, although perhaps slightly bulky, way of handling the repeated 5 term at the beginning. The terms strictly increase thereafter.

Part 2

You are given an integer greater than 1. Write a script to find the home prime of the given number.

Solution

use strict;
use warnings;
use bigint;
use Math::Primality qw/is_prime/;

sub prime_factor{
    my $x = shift(@_); 
    my @factors;    
    for (my $y = 2; $y <= $x; $y++){
        next if $x % $y;
        $x /= $y;
        push @factors, $y;
        redo;
    }
    return @factors;  
}

sub home_prime{
    my($n) = @_;
    return $n if is_prime($n);
    my $s = $n;
    {
        $s = join("", prime_factor($s));
        redo if !is_prime($s);
    }
    return $s;
}

MAIN:{
    print home_prime(10) . "\n";
    print home_prime(16) . "\n";
}

Sample Run

$ perl perl/ch-2.pl
773
31636373

Notes

So you think eight is low

Calculating HP(8) should be an easy go

Take the long way home

Take the long way home

The second part of this week's challenge was a lot of fun as it presented some unexpected behavior. Here we are asked to compute the Home Prime of any given number. The process for doing so is, given N to take the prime factors for N and concatenate them together. If the result is prime then we are done, that is the Home Prime of N, typically written HP(N). This is an easy process to repeat, and in many cases the computation is a very quick one. However, in some cases, the size of the interim numbers on the path to HP(N) grow extremely large and the computation bogs down, whence take the long way home! As an example, the computation of HP(8) is still running after 24 hours on my M1 Mac Mini.

References

Challenge 168

Home Prime

Take the Long Way Home