The Bear's Den

Enter at your own risk

Perrin's Home

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]


Solution

This is a reproduction of my solution dated 6 Jun 2022.


The solution to task 2 from challenge 154 with different starting values could be reused to solve this task. But this would be boring and thus the task will be generalized here.

The excellent Math::Prime::Util ennobles List::Gen by referencing it in the “SEE ALSO” section. Indeed, it looks very cool but comes with a serious flaw: There has not been any development for over 10 years and one of the tests is broken. Needed --force to install. IMHO the test result is ok, but the expected outcome is not.

"Failed test 'map & \(1 .. 3), 1 .. 2'"

Building a generator for a sequence having the initial values S(1),...,S(k) and a recurrence relation defined by a linear combination of preceding elements:
S(n) = F(1) * S(n - k) + ... + F(k) * S(n - 1) for n > k.
and taking unique primes thereof.

Some known prime sequences:
IV=0,1   F=1,1: Fibonacci
IV=2,1   F=1,1: Lucas
IV=1,1,1 F=1,1: Padovan
IV=3,0,2 F=1,1: Perrin (default)
IV=0,1   F=1,2: Pell
IV=0,1   F=2,1: Jacobsthal
sub lin_recur_primes ($s, $f) {

    # Lazily extend the initial sequence using the recurrence relation.
    ($s + iterate {($s = [$s->@[1 .. $#$s],
                    tuples($f, $s)->map('product @$_')->sum])->[-1]
        })->uniq->filter(sub {is_prime $_});
}

See the full solution to task 1.

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) 

Solution

There is nothing special in implementing the procedure.

Perl

use strict;
use warnings;
use experimental 'signatures';
use Math::Prime::Util 'factor';

sub home_prime ($n) {
    while () {
        my @factor = factor $n;
        return shift @factor if @factor == 1;
        $n = join '', @factor;
    }
}

See the full solution to task 2.

J

NB. find the "home prime" for y
home_prime =: _(adverb define)
  NB. factors of y
  factors =. q:

  NB. convert numbers to boxed strings
  to_boxed_str =. <@(0&":"0)

  NB. remove outer boxes
  raze =. ;

  NB. convert (numeric) string to number
  to_num =. 0&".

  NB. apply left operand repeatedly to previous result
  NB. while the result changes
  while_changes =. ^:_

  NB. find factors, convert to strings, join and convert
  NB. to integer
  NB. repeat while the result changes
  to_num @ raze @: to_boxed_str @ factors while_changes f.
)

See the full solution.