Perming Perl

plus Padovan primes

Weekly challenge 154 — 28 February 2022

Week 154 - 28 Feb 2022

Task 2

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.

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

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);

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

The content of this website which has been created by

Peter Campbell Smith is hereby placed in the public domain

Peter Campbell Smith is hereby placed in the public domain