The Fortunate Son

Wherein as we say something witty…

THE WEEKLY CHALLENGE – PERL & RAKU #155 Task 1

---

“Advocates of capitalism are very apt to appeal to the sacred principles of liberty, which are embodied in one maxim: The fortunate must not be restrained in the exercise of tyranny over the unfortunate.“

— Bertrand Russell

---

Fortunate Numbers

Submitted by: Mohammad S Anwar

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.

Expected Output

3, 5, 7, 13, 17, 19, 23, 37

ANALYSIS

For those of you following along at home, we recently had a discussion on the “square-free integers”, and how they seem to pop up unexpectedly all over various topics in number theory. In the context of today’s task, I will take the time to point out that the product of the first n prime numbers is the same as a prime degeneration with a maximal amount of discrete factors — that is with no exponents. So in other words we are talking about the largest square-free integer that we can create from n number of factors.

Sow how about that? I don’t want to say: “I told you so”, but, well…

You know…

To rephrase the description then, the fortunate numbers correspond to a list of positive deltas required to make the largest square-free integer with a continuous sequential prime factorization from 2, prime.

Ok, I grant that might not make things any clearer.

So we need to produce a list of primes, and from that list of cumulative products as we multiply in each successive term. Then from each of these products we need to first add 3 to make it odd and check for primality.

Because the promorial will always be have 2 as a factor it will always be even. We would minimally make this odd by adding 1, but 1 is always excluded from the fortunate numbers so we immediately jump to 3.

Likewise for testing a number for primality we can skip the calculation for 2, because we know we’ve made the candidate odd already. So we can start at 3 and increment upwards by 2s from there. We test repeatedly until we are prime.

There’s one last step though, which is to find 8 distinct terms and sort them. Simply put, we need to make sure we gather terms until we have enough. As it’s evident the list is not necessarily ordered, this raises the possibility that somewhere along the line the skipped-over value of 11 may suddenly arise, say at position 1142 or such. I don’t see that happening but at the moment I don’t see any reason to exclude the possibility. The proof that it won’t will be left as an exercise to the reader.

What we will do though is assume it will not, and interpret the directive as “the first 8 distinct terms, sorted”, which is slightly different than stated and less absolute. We will just collect terms until we find 8 values and then dump the buffer.

METHOD

PERL 5 SOLUTION

In Perl we generate primes one-by-one and multiply them into an aggregate product. This is the latest primorial in the sequence. From there we start by adding 3 and checking for primality, and then adding by 2s to successive values until a number is found to be prime. When we do, we make augment a hash entry for the output array, and move on to the next. We stop when we have 8.

For the prime generator I’ve taken it and reworked it as returning an iterator coderef closed around a list of primes; calling the iterator now generates and returns the next prime indefinitely. Cool beans.

my $pgen = prime_generator();
my @primes;
my $primorial = 1;              ## multiplicative identity
my %fortunate;

while ( keys %fortunate < 8 ) {
    push @primes, $pgen->();
    $primorial *= $primes[-1];

    ## loop through values for $f until a prime number is found
    my $f = 1;
    my $candidate;
    FORTUNATE: while ( $f += 2 ) {
        $candidate = $primorial + $f;
        my $sqrt_candidate = int sqrt( $candidate );
        for ( my $test = 3; $test <= $sqrt_candidate; $test += 2 ) {
            next FORTUNATE if $candidate % $test == 0;
        }
        $fortunate{$f}++;
        last FORTUNATE;
    }
}
    
say join ', ', sort {$a<=>$b} keys %fortunate;


sub prime_generator ( ) {
## returns an iterator closure that always delivers the next prime
    state @primes;
    
    return sub {
        if ( @primes < 2 ) {
            push @primes, @primes == 0 ? 2 : 3;
            return $primes[-1];
        }
    
        my $candidate = $primes[-1] ;
        CANDIDATE: while ( $candidate += 2 ) {
            my $sqrt_candidate = sqrt( $candidate );
            for my $test ( @primes ) {
                next CANDIDATE if $candidate % $test == 0;
                last if $test > $sqrt_candidate;
            }
            push @primes, $candidate;
            return $candidate;
        }
    }
}

Raku Solution

In Raku the process becomes one complex chained function:

1. In the first line we take the triangular reduction product of an infinite prime sequence that has been sliced to the first $quan number of elements, corresponding to the number of fortunate numbers we want to create. This creates a list of primorials to process.
2. In the second line we map individual elements from that list to the result of creating an infinite list of values starting at the initial element value plus 2, and then finding the first prime number in the sequence. The we subtract the initial value to arrive at the difference, which is the fortunate number.
3. Then we output the final list of fortunate numbers we’ve created.

I love this data flow.

unit sub MAIN ($quan = 20) ;

    ([\*] ((1..*).grep: *.is-prime)[0..$quan])
        .map({($_+2...Inf).first(*.is-prime) - $_})
        .say ;