Bigint week

Weekly challenge 155 — 7 March 2022

Week 155 - 7 Mar 2022

Task 1

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.

Example 1: The first Fortunate number is 3.

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

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

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