Perl Weekly Challenge 168.
My solutions (task 1 and task 2 ) to the The Weekly Challenge - 168.
Task 1: Perrin Prime
Submitted by: Roger Bell_West
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]
A simple solution is to iteratively generate Perrin numbers
and test them for primality. There is a slight problem in that
the first few Perrin numbers are prime, are produced out of
order and have repetitions. Thus, I could start slightly
ahead in the sequence or keep track of seen numbers and sort
the resulting array. This leads to a 3-liner, using is_prime
from Math:::Prime::Util to test primeness.
perl -d -MMath::Prime::Util=is_prime -E '$N=shift; @p=(3,0,2); while(@pp<$N){
push @p, $p=$p[-3]+$p[-2]; $pp{$p}=1, push @pp,$p if is_prime($p) and !$pp{$p}; }
say join " ", sort {$a<=>$b} @pp;' 13
Results:
2 3 5 7 17 29 277 367 853 14197 43721 1442968193 792606555396977
The complete code is:
1 # Perl weekly challenge 168
2 # Task 1: Perrin prime
3 #
4 # See https://wlmb.github.io/2022/06/06/PWC168/#task-1-perrin-prime
5 use v5.12;
6 use warnings;
7 use bigint;
8 use Math::Prime::Util qw(is_prime);
9 die "Usage: $0 N\n to write the first N Perrin Primes" unless @ARGV;
10 my $N=shift;
11 my @last_perrins=(3,0,2);
12 my @perrin_primes;
13 my %seen;
14 while(@perrin_primes<$N){
15 push @last_perrins, my $perrin=$last_perrins[-3]+$last_perrins[-2];
16 shift @last_perrins; # no need to keep old Perrins
17 $seen{$perrin}=1, push @perrin_primes, $perrin if is_prime($perrin) and !$seen{$perrin};
18 }
19 say join " ", sort {$a<=>$b} @perrin_primes;
Example:
./ch-1.pl 13
Results:
2 3 5 7 17 29 277 367 853 14197 43721 1442968193 792606555396977
A curious example:
./ch-1.pl 1
Results:
3
Three is indeed a Perrin prime but, is it the first? I’m not sure which is the convention, but surely it is not too important.
A final example:
./ch-1.pl 17|fmt
Results:
2 3 5 7 17 29 277 367 853 14197 43721 1442968193 792606555396977
187278659180417234321 66241160488780141071579864797
22584751787583336797527561822649328254745329
29918426252927024136988188355201180399482197
The last numbers are much larger than what fits in an integer,
thus the use bigint in line 7.
Task 2: Home Prime
Submitted by: Mohammad S Anwar
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
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.
This task is simple with the appropriate tools to factor a
number, with ordered factors, and to test for primeness. As
both are included in the package Math::Prime::Util the task
may be solved with a oneliner.
perl -MMath::Prime::Util=factor,is_prime -E '
for(@ARGV){$N=$_; $N=join "", factor($N) while(!is_prime($N)); say "HP$_=$N"}' 10 25 55 511 773
Results:
HP10=773
HP25=773
HP55=773
HP511=773
HP773=773
which confirms the correctness of the sequence discussed in the task description.
Another example:
perl -MMath::Prime::Util=factor,is_prime -E '
for(@ARGV){$N=$_; $N=join "", factor($N) while(!is_prime($N)); say "HP$_=$N"}' 2 3 4 5 6 7 8 9 10
Results:
HP2=2
HP3=3
HP4=211
HP5=5
HP6=23
HP7=7
HP8=3331113965338635107
HP9=311
HP10=773
the first few home primes.
The full version is
1 # Perl weekly challenge 168
2 # Task 2: Home prime
3 #
4 # See https://wlmb.github.io/2022/06/06/PWC168/#task-2-home-prime
5 use v5.12;
6 use warnings;
7 use Math::Prime::Util qw(is_prime factor);
8 die "Usage: $0 n1 [n2... ]\n to obtain the home primes of n1..." unless @ARGV;
9 for(@ARGV){
10 say("The argument ($_) should have been >=2"), next unless $_>=2;
11 my $N=$_;
12 $N=join "", factor($N) while(!is_prime($N));
13 say "HP$_=$N"
14 }
Example:
./ch-2.pl 2 3 4 5 6 7 8 9 10
Results:
HP2=2
HP3=3
HP4=211
HP5=5
HP6=23
HP7=7
HP8=3331113965338635107
HP9=311
HP10=773