Peter
Peter Campbell Smith

Bigint week

Weekly challenge 155 — 7 March 2022

Week 155: 7 Mar 2022

Task 1

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.

Script


#!/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 

 

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