### 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
```

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;
```

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.

##### Example:

As given in the Wikipedia page,

```
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;
}
```

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;
}
```