Task — Padovan primes

A Padovan Prime is a Padovan Number that’s also prime. In number theory, the Padovan sequence is the sequence of integers P(n) defined by:

• P(0) = P(1) = P(2) = 1, and then
• P(n) = P(n-2) + P(n-3)

Write a script to compute first 10 distinct Padovan Primes.

Examples

The first few Padovan Numbers are:
1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37 

Analysis

We are given the definition of the Padovan series and asked to find the first 10 distinct members of the series that are prime. The complication is that the 10th exceeds the largest value that Perl can hold as an integer.

Generating the series is easy, and each successive number requires only the addition of two previous ones, so all that is needed for that is a simple extended add - ie a function that will add two arbitrarily long integers. I though of writing that myself, but Math::Bigint does the job better than I could.

However, what really makes Math::Bigint worth it is that Math::Prime::Util contains the function is_prime(), which works with big integers expressed in the same format as Math::Bigint - ie as a simple ASCII string of digits.

#!/usr/bin/perl

# Peter Campbell Smith - 2022-02-28
# PWC 154 task 2

use v5.28;
use strict;
use utf8;
use Math::Prime::Util 'is_prime';
use Math::BigInt lib => 'GMP';

my (@p, $n, $string, $count);

# as in challenge text
$p[0] = $p[1] = $p[2] = '1';

# make successive Padovan numbers
for ($n = 3; $count <= 10; $n ++) {
    $p[$n] = Math::BigInt->new($p[$n - 2]);
    $p[$n]->badd($p[$n - 3]);
    
    # but is it prime?
    if (is_prime($p[$n])) {
        $string .= qq[$p[$n], ];
        $count ++;
    }
}

# eliminate the repeated '2' and the final ', '
say qq[Padovan primes:\n] . substr($string, 3, -2); 

Output

Padovan primes:
2, 3, 5, 7, 37, 151, 3329, 23833, 13091204281, 
   3093215881333057