Peter
Peter Campbell Smith

Fun with primes

Weekly challenge 168 — 6 June 2022

Week 168: 6 Jun 2022

Task 1

Task — Perrin prime

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.

Examples

f(13) = [2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 
   1442968193, 792606555396977]

Analysis

So far as I can see this sequence has no obvious practical use, but that's what pure mathematicians like.

Looking at the supplied value of f[13] it seems wise to invoke our old friend Math::BigInt, and the only other quirk is that some early numbers - such as 5 - appear more than once so duplicates need to be avoided.

We can keep going and establish that f[23] is: 36316401639924481580503219791016345234244670705329899405 89376200895999542521324121865744873084026078365592113103 82905704431937109345826731415063277024792603788022650498 09362579106024819480188413624541435624405371905148981737 76176693598426395086189616722660098879586330664613823090 19736040977943759168952083749283051316305477706149140125 98175725461977531098571999932368819716562554010397998205 79630315398215866349742611432329007353997352494443986017 31792283336352335183571166321225239882712620758095377946 97982652185145064971140674770642597897997331353245241665 20280952689291443318735365943242441087374207019201381566 62288736104738328478689308743984566009720499556608846083 5424395601898782600822606786314286293

... but beyond that is_prime() begins to struggle.

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2022-06-06
# PWC 168 task 1

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

my (@perrin, $j, $count, %seen);

# initialise
@perrin = (3, 0, 2);
$count = 1;

# calculate perrin primes until 13 unique ones found
for $j (0 .. 9999) {
    
    # get next term
    if ($j > 2) {
        $perrin[$j] = Math::BigInt->new($perrin[$j - 2]);
        $perrin[$j]->badd($perrin[$j - 3]);
    }
    
    # no good unless prime and not already seen
    next if defined $seen{$perrin[$j]};
    next unless is_prime($perrin[$j]);
    
    # result!
    $seen{$perrin[$j]} = 1;
    say qq[f[$count] = $perrin[$j]];
    last if $count ++ == 13;
}

Output


f[1] = 3
f[2] = 2
f[3] = 5
f[4] = 7
f[5] = 17
f[6] = 29
f[7] = 277
f[8] = 367
f[9] = 853
f[10] = 14197
f[11] = 43721
f[12] = 1442968193
f[13] = 792606555396977

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain