Perl Weekly Challenge: Week 168
Challenge 1:
Perrin Prime
The
Perrin sequenceis defined to start with[3, 0, 2]; after that, term N is the sum of termsN-2andN-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 - 2nd and N - 3rd 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;
}