Perl Weekly Challenge 147: Truncatable Prime

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

We are asked to provide the first 20 entries of the sequence A024785 in the on-line encyclopedia of integer sequences.

The pages of this sequence contains a Python implementation (by Michael S. Branicky) to generate all of the left-truncatable primes:

from sympy import isprime

def alst ():
    primes, alst = [2, 3, 5, 7], []

    while len (primes) > 0:
        alst += sorted (primes)
        cand = set (int (d + str (p)) for p in primes for d in "123456789")
        primes = [c for c in cand if isprime (c)]
    return alst

print (alst ())

We can easily adapt this to generate the first 20 in order.

We start off by importing the is_prime routine from Math::Prime::Util:

use Math::Prime::Util qw [is_prime];

This makes it easy to check whether a number is a prime.

Then we initialize an array with the single digit primes, and a counter to keep track of the number of primes we have produced:

my @todo  = qw [2 3 5 7];
my $count = 20;

print "$_ " for @todo;
$count -= @todo;

Now we can iterate. In each iteration, for each prime of the previous iteration, we prepend each of the 9 different digits, and check whether the result is prime. If so, this is a left-truncatable prime, and we print and keep it:

MAIN: while (@todo) {
    my @next;
    for my $d (1 .. 9) {
        foreach my $p (@todo) {
            my $candidate = "$d$p";
            next unless is_prime ($candidate);
            print "$candidate ";
            last MAIN if -- $count <= 0;
            push @next   => $candidate;
        }
    }
    @todo = @next;
}

Find the full program on GitHub.

We don't have access to a function which returns whether its argument is a prime number or not in all languages. Nor does every language allow us to just stick strings together and have it be a number. bc is such a language. First, we define a method is_prime:

define is_prime (p) {
    auto d
    if (p == 2) {return 1}
    if (p % 2 == 0) {return 0}
    for (d = 3; d * d <= p; d += 2) {
        if (p % d == 0) {return 0}
    }
    return 1
}

bc doesn't have array literals, or a function to get the size of an array, so we have to do a bit more work to do the initializations:

todo [1] = 2
todo [2] = 3
todo [3] = 5
todo [4] = 7
high = 4

for (i = 1; i <= high; i ++) {
    print todo [i], " "
}

count = 20 - high

To get the a next candidate for a truncatable prime, instead of using string concatenation, we just arithmetic, keeping track of a power of 10:

pow = 10
while (count > 0) {
    new_high = 0
    for (d = 1; d <= 9 && count > 0; d ++) {
        for (i = 1; i <= high && count > 0; i ++) {
            candidate = d * pow + todo [i]
            if (is_prime (candidate)) {
                print candidate, " "
                new_high = new_high + 1
                count = count - 1
                next [new_high] = candidate
            }
        }
    }
    for (j = 1; j <= new_high; j ++) {
        todo [j] = next [j]
    }
    high = new_high
    pow = pow * 10
}

Find the full program on GitHub.