# Perl Weekly Challenge 168.

My solutions (task 1 and task 2 ) to the The Weekly Challenge - 168.

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

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

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  #
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
``````
Written on June 6, 2022