Task — Fortunate numbers

Write a script to produce first 8 Fortunate Numbers (unique and sorted). According to Wikipedia a Fortunate number, named after Reo Fortune, is the smallest integer m > 1 such that, for a given positive integer n, pn# + m is a prime number, where the primorial pn# is the product of the first n prime numbers.

Examples

Example 1:
The first Fortunate number is 3.

Analysis

The definition of Fortunate numbers leads to the following basic algorithm for finding them:

• Loop over n = 1 to something big
• Calculate the product of the first n primes (pn)
• Loop over m = 2 to something else big
• Calculate pn + m and check if it's prime

However, pn increases very steeply and p17 is the largest that will fit into 64 bits, so Bigint is needed to represent pn for larger ones. And also, pn + m will be bigint-ish which makes it hard to determine its primality. Math::Prime::Util can however do that, though for very large numbers it's guessing a bit.

My algorithm finds the first 20 Fortunate numbers - confirmed by the OEIS - in a couple of seconds even on a slow processor, although it is not immediately obvious that there isn't example of, say m = 11, for some huge n that I didn't explore.

People cleverer than me will have thought (or known) of a better way, but mine works and is easy to understand.

#!/usr/bin/perl

# Peter Campbell Smith - 2022-03-07
# PWC 155 task 1

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

my ($limit, $lines, @pn, $try, %results, $r);

# populate $pn[$n] up to $pn[$limit]
$limit = 100;
make_pn($limit);

# loop over n and m as defined above
N: for my $n (2 .. $limit) {
    for my $m (2 .. 150) {
        
        # calculate pn# + m
        $try = Math::BigInt->new($pn[$n]); 
        $try = $try->badd($m);
        
        # if that's prime we have a result
        if (is_prime($try)) {
            $results{sprintf('%08d', $m)} = 1;
            next N;
        }
    }
}

# format results as requested
for $r (sort keys %results) {
    print qq[First 8 Fortunate numbers: ] unless $lines ++;
    print qq[\nand then: ] if $lines == 9;
    print '' . ($r + 0) . ' ';
}
print qq[\n];

#---

sub make_pn {
    
    my ($arg, $prev, $n, $j);
    
    # populate $pn[$n] up to $pn[$limit]
    $arg = shift;
    $n = 1;
    $pn[1] = Math::BigInt->new(1);
    for ($j = 2; $n < $arg; $j ++) {
        next unless is_prime($j);
        $n ++;
        $pn[$n] = Math::BigInt->new($pn[$n - 1]);
        $pn[$n] = $pn[$n]->bmul($j);
    }
}
        

Output

First 8 Fortunate numbers: 3 5 7 13 17 19 23 37 
and then: 47 59 61 67 71 79 89 101 103 107 109 127