Add Another Prime to the Pile

Wherein the hits just keep on coming…

THE WEEKLY CHALLENGE – PERL & RAKU #158 Task 1


I appreciate the additional additives and preservatives that help sell a project, but I’m sticking to what works best for me. I gotta sell the album live on stage and make people believe in the songs.

Busta Rhymes


Additive Primes

Submitted by: Mohammad S Anwar

Write a script to find out all Additive Primes ≦ 100.

Additive primes are prime numbers for which the sum of their decimal digits are also primes.

Output

2, 3, 5, 7, 11, 23, 29, 41, 43, 47, 61, 67, 83, 89

ANALYSIS

You know, sometimes when I do these problems I like to pretend that I’m not good at math. Which is to say I choose to regard the problem as a computing problem, rather than a math problem, or or even more broadly as a problem in search of a structure that will solve it, rather than any specific answer.

Or put another way if the simple form raises more questions than it answers I’ll solve a more generalized version with more unknowns, looking for the big picture, or just play around with the method instead of the particulars.

In this problem we need a bunch of prime numbers. A quick bit of mathematical reasoning tells us

  1. that 100 is not a additive prime, as it adds to 1
  2. the that largest digit-sum we’ll need to deal with is for the value 99, where 9 + 9 = 18.
  3. thus, using preexisting knowledge we only need to consider the primes 2, 3, 5, 7, 11, 13, and 17. In fact we’ll only need the first four of these, up to the square root of 100.

But you know what? We’re going to pretend we don’t know that, and instead compute as many primes as required. Along the way we’ll make the upper limit user-configurable, which will allow us to find the number 101 should we wish, which by the looks of it is an additive prime.

What we’ll need to do is make a list of primes that contains every prime less than the largest value we have tried to date. The digit sum will always be less than or equal to the value, so we’re covered in that department if we set the limit at the larger value. If at any point we exceed the last prime found, we’ll just add another prime to the list.

Along the way, we can construct our lookup hash as we go to check for primality.

So over the range from 1 to 100, or whatever upper limit we request, we first check to make sure the candidate is prime, then if it is we further check its digit sum. If both of these prime checks are true then we add the candidate to our output list of additive primes.

METHOD

PERL 5 SOLUTION

For amusement I’ve decided to create an anonymous function closed around a growing list of prime numbers. This returns the next prime number as an iterator but we’re not going to use that today; rather we’re going to consult the underlying list it keeps updated, and for good measure we’ll add in a parallel hash structure with primes as keys as well to make prime checks easy. I mean, that is the whole purpose of creating the primes in the first place. Might as well get it done at the source.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';

use List::Util qw( sum0 );

my @primes;
my %lookup;
my @additives;

## make a closed prime iterator function
## modified to add to the prime lookup hash
my $pg =  sub {
    if ( @primes < 2 ) {
        push @primes, @primes == 0 ? 2 : 3;
        $lookup{ $primes[-1] } = 1;
        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;
        $lookup{ $candidate } = 1;
        return $candidate;
    }
} ;
$pg->();        ## init the prime array with 2

my $limit = shift @ARGV // 100;

## look at the numbers 1 to $limit,
## checking each for primality and primality in the digit sum
for ( 1..$limit ) {
    $pg->() if $primes[-1] <= $_ ;
    next unless $lookup{$_} ;
    my $sum = sum0( split //, $_ );
    push @additives, $_ if  $lookup{$sum};
}

say join ', ',  @additives;

Raku Solution

In Raku we treat the process functionally with a series of chained grep methods, each using whatever code to first to filter out first non-primes, then those whose digit sums are not prime.

The closures in the whatever code somewhat parallels the anonymous function that produces the prime list in the Perl code, which is pretty neat. As is often the case in Raku, the solution is kind of ridiculously compact.

unit sub MAIN ( $limit = 100) ;

put (^$limit).grep(*.is-prime )
             .grep(*.comb.sum.is-prime);


The Perl Weekly Challenge, that idyllic glade wherein we stumble upon the holes for these sweet descents, is now known as

The Weekly Challenge – Perl and Raku

It is the creation of the lovely Mohammad Sajid Anwar and a veritable swarm of contributors from all over the world, who gather, as might be expected, weekly online to solve puzzles. Everyone is encouraged to visit, learn and contribute at

https://theweeklychallenge.org

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s