Perl Weekly Challenge: Week 168

Challenge 1:

Perrin Prime

The `Perrin sequence` is defined to start with `[3, 0, 2]`; after that, term N is the sum of terms `N-2` and `N-3`. (So it continues 3, 2, 5, 5, 7, ….)

A Perrin prime is a number in the Perrin sequence which is also a prime number.

Calculate the first `13 Perrin Primes`.

f(13) = [2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977]

In Raku we can solve this as a one-liner:

``````(3,0,2, -> \$i, \$j, \$ { \$i + \$j} ... ∞).grep({ .is-prime }).unique[^13].sort.join(q{, }).say
``````

(Full code on Github.)

The first part creates a lazy list. It starts off with the values `3`, `0`, `2` and then computes the next Perrin value by summing the `N - 2`nd and `N - 3`rd terms as the spec suggests. I learned about a nifty Raku feature today. If you need an argument as a placeholder but don't want to name it because you aren't going to use it, you can just define it anonymously as a sigil like `\$` here. Because this is a lazy list, the next value is only computed as needed so it is very efficient.

Next we `.grep()` through these Perrin numbers for ones which are prime with `.is-prime()`. Because some of these values can be repeated we also use `.unique()` to weed out duplicates. `[^13]` means we only want the first 13 Perrin Primes. We also sort them. Finally we print the results nicely with `.join()` and `.say()`.

Perl is as usual more verbose than raku. For a start we need an `isPrime()` function as that is not built in. Fortunately this has come up many times in past challenges so I just cut and pasted my tried and true version.

``````my @perrins = (3, 0, 2);
my @perrinPrimes;
``````

We create a list to hold the Perrin sequence, seeding it with the first three values namely, `3`, `0` and `2`. We also define another list to hold the resulting Perrin Primes.

``````while (scalar @perrinPrimes < 13) {
``````

We loop until we have collected 13 Perrin Primes.

``````    if (isPrime(\$perrins[2]) && ! grep { \$_ == \$perrins[2] } @perrinPrimes) {
``````

If the last element of our `@perrins` list is prime and if it is not already in `@perrinPrimes`...

``````        push @perrinPrimes, \$perrins[2];
``````

...it is added to `@perrinPrimes`.

``````    }

push @perrins,  \$perrins[0] + \$perrins[1];
shift @perrins;
``````

Then the next Perrin number is calculated and added to `@perrins` while the first one in the list is removed. This keeps the list three elements long.

``````}

say join q{, }, sort {\$a <=> \$b} @perrinPrimes;
``````

(Full code on Github.)

Finally, when we have 13 Perrin Primes, the list is numerically sorted and printed nicely.

Challenge 2:

Home Prime

You are given an integer greater than 1.

Write a script to find the home prime of the given number.

In number theory, the home prime HP(n) of an integer n greater than 1 is the prime number obtained by repeatedly factoring the increasing concatenation of prime factors including repetitions.

Further information can be found on Wikipedia and OEIS.

Example:

``````HP(10) = 773, as 10 factors as 2×5 yielding HP10(1) = 25, 25 factors as 5×5 yielding HP10(2) = HP25(1) = 55, 55 = 5×11 implies HP10(3) = HP25(2) = HP55(1) = 511, and 511 = 7×73 gives HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773, a prime number.
``````

The high-level algorithm as illustrated in Raku is this:

``````my \$hp = \$n;
``````

Start by setting the resulting Home Prime (`\$hp`) to the value of the integer you were given (`\$n`.)

``````until \$hp.is-prime {
``````

Until `\$hp` is a prime number...

``````    my @factors = factorize(\$hp);
``````

Get the prime factors.

``````    \$hp = @factors.join(q{}).Int;
``````

Smoosh (that's the technical term) the prime factors together. `.join()` converts its result to a string so we also need `.int()` to make it into a number again. This is the next value of `\$hp`.

``````}

say \$hp;
``````

Once we have a prime number, print it.

Most of the work is done by the `factorize()` function which produces the prime factors. I already had code for this I had used for previous challenges which looked like this:

``````sub factorize(Int \$n, @primeFactors) {
if \$n < 2 {
return;
}

my \$i = 0;
my @primes = (1 .. ∞).grep({ .is-prime });
my \$p = @primes[\$i];

while \$p <= \$n {

if \$n %% \$p {
@primeFactors.push(\$p);
factorize(\$n div \$p, @primeFactors);
return;
}
\$p = @primes[\$i++];
}
}
``````

It uses the Sieve of Eratosthenes and is called recursively. Although it worked ok for HP(10), it was horribly slow for HP(8) which is 3,331,113,965,338,635,107.

So I rewrote the function using a different, non-recursive algorithm as shown below:

``````sub factorize(Int \$N) {
my \$n = \$N;
my @primeFactors;

while \$n %% 2 {
@primeFactors.push(2);
\$n /= 2;;
}

loop (my \$i = 3; \$i <= \$n.sqrt; \$i += 2)  {
while (\$n %% \$i) {
@primeFactors.push(\$i);
\$n /= \$i;
}
}

if \$n > 2 {
@primeFactors.push(\$n);
}

return @primeFactors;
}
``````

(Full code on Github.)

This works a lot better but still founders on HP(20). I did not investigate further into what can be done about this.

For Perl, the main loop looks like this:

``````my \$hp = \$n;
until (isPrime(\$hp)) {
my @factors = factorize(\$hp);
\$hp = int join q{}, @factors;
}

say \$hp;
``````

And `factorize()` is translated like this:

``````sub factorize {
my (\$n) = @_;
my @primeFactors;

while (\$n % 2 == 0) {
push @primeFactors, 2;
\$n /=  2;
}

for (my \$i = 3; \$i <= sqrt \$n; \$i += 2)  {
while (\$n % \$i == 0) {
push @primeFactors, \$i;
\$n /= \$i;
}
}

if (\$n > 2) {
push @primeFactors, \$n;
}

return @primeFactors;
}
``````

(Full code on Github.)