primes-rimes-imes-mes-es-s

Wherein as we trim the extraneous fat we remain true to our roots…

THE WEEKLY CHALLENGE – PERL & RAKU #147

---

“My glass is getting shorter
On whiskey, ice and water“

— Wire (Newman/Lewis/Gilbert/Grey) The Agfers of Kodack

---

Truncatable Prime

Submitted by: Mohammad S Anwar

Write a script to generate first 20 left-truncatable prime numbers in base 10.

In number theory, a left-truncatable prime is a prime number which, in a given base, contains no 0, and if the leading left digit is successively removed, then all resulting numbers are primes.

Example

9137 is one such left-truncatable prime since 9137, 137, 37 and 7 are all prime numbers.

ANALYSIS

Number Theory is so weird. Take two ideas, as tenuously related as any you can come up with, and weld them together, then look and see what Frankenstein’s monster you’ve created, just to see if anything can be inferred from the data.

Which itself is likely to be another question, another derivitive in search of a place in some greater fabric of meaning.

There’s a certain devil-may-care undercurrent to it all, consequence be damned: “With my new rabbit-fish soldiers my army will be unstoppable! I hold the powers of life and death itself in my hands!”

The mad-scientist metaphor is particularly apropos as the patterns detected will be nearly by definition unobvious. After all, if it were obvious it would probably just be absorbed into some sort of more mainstream mathematics. What is being looked for in Number Theory are the deep connections, tendrils left over from the creation of the universe itself, or even before and beyond the creation. After all, math exists, metaphysically, outside the universe.

Or perhaps that premise too can be disputed. Nothing is off the table. We are investigating the hairy edge-cases of reality with a ferver that aligns with the mystical. Newton, it is known now, was an alchemist.

“There are more things in heaven and earth, Horatio,
Than are dreamt of in your philosophy.”

— William Shakespeare, Hamlet

Why would anyone do this? Well that at least is obvious: because it’s there, of course. If you could stare into the center of creation, why wouldn’t you?

Bring sunglasses.

METHOD

As we have no idea of how many primes we will require, we’ll need to rework our prime generator as an iterator. This maintains an internal list, computing and returning the next prime, whatever that is, when called. The primes produced by calling the generator are then placed in a hash for easy lookup, as we’ll need to consult our list of already-computed primes often, with random access.

When we have a new prime, we hand it to a truncatable() subroutine to see how it fares. Inside a loop the leftmost digit is lopped off using substr() and the value is rechecked. If at any time the lopped number is no longer prime, 0 is returned, and if it successfully runs the gauntlet we return 1. This subroutine is used for a loop conditional when validating each candidate prime. If the test is passed we add the candidate to the list of left-trancatables and continue.

I originally intended to skip the trivial cases of single-digit primes as uninteresting, but was swayed by finding out that the casual definition notwithstanding this is not in fact the way these numbers are commonly determined. Here is the presumed-definitive entry from the Online Encyclopedia of Integer Sequences:

A024785

Left-truncatable primes: every suffix is prime and no digits are zero.

Because our algorithm runs quickly we’ll compute a thousand instead of 20.

PERL 5 SOLUTION

The function get_next_prime() keeps an internal prime list as a state variable, which it uses to validate candidates counting by 2s from the last prime found, locating and returning the next prime in sequence. The primes are requested by the main driver, which checks each for left-runcatability and then adds it to a hash of primes found, which is in turn used as a fast lookup for the thruncating routine. As the truncated numbers will always be smaller than the last prime added this hash will always be complete within the range required.

Doing things this way avoids explicitly constructing an additional loop to preprocess the primes into a hash for quick random-access to the values, hijacking the existing loop instead.

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


my $prime_lookup;
my @lt_primes;

while ( @lt_primes <= 100 ) { 
    my $candidate = get_next_prime();
    $prime_lookup->{ $candidate } = 1;
    next unless left_truncatable( $candidate, $prime_lookup );
    $candidate and push @lt_primes, $candidate;
}

say $_ for @lt_primes;

sub get_next_prime ( ) {
## an iterator that delivers the next prime
    state @primes;
    
    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;
    }
}

sub left_truncatable ( $val, $lookup ) {
    return 0 if $val =~ /0/;
    
    while ( 1 ) {
        substr $val, 0, 1, '';
        last unless $val;
        return 0 unless $lookup->{$val};
    }
    return 1;
}