Task — Truncatable prime

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 leftmost digit is successively removed, then all resulting numbers are primes.

Examples

Example 1:
9137 is a left-truncatable prime since 9137, 137,
37 and 7 are all prime numbers.

Analysis

In principle this is easy enough: generate the primes using a sieve of our good friend Eratosthenes, discard any containing zeroes, and check the remainder for being left-truncatable.

The first 4 LTPs are 2, 3, 5 and 7, and the next 11 LTPs are only 2 digits - they range from 13 to 97, and 5 more - 113, 137, 167, 173 and 197 complete the required 20.

However, had the task asked for the first 1000 LTPs it would be worth applying a little optimisation. For example, the last digit of an LTP can only be 3 or 7, since any number ending in 0, 2, 4, 5, 6 or 8 is not prime, and any ending in 1 or 9 will fail the LTP test when only that digit remains (in modern maths, 1 is not regarded as a prime).

So doing that I found 1000 LTPs in 3 seconds: the 1000th is 8391283.

I then tried for 2000. It took quite a while because they get steadily sparser, and my computer ran out of memory before getting to the 2000th - it quit at 99962683.That's partly because the OEIS says there are only 4260 of them and the last is 357686312646216567629137 which is way beyond Perl's max integer.

#!/usr/bin/perl

# Peter Campbell Smith - 2022-01-10
# PWC 147 task 1

use v5.28;
use warnings;
use strict;

my ($seeking, $prime_index, $from, $to, $test, $this, @not_a_prime, $string, $count,
    $start, $factor, $multiple, $line);

# initialise
$seeking = 200;   # how many to find
$count = 0;      # how many found
say qq[\nFirst $seeking left-truncatable prime numbers:];

# find primes in ranges of 1000
$line = '';
RANGE: for ($from = 1; ; $from += 1000) {
    $to = $from + 999;

    # loop over all the possible factors, ie primes < sqrt($to)
    for $factor (2 .. int(sqrt($to))) {
        next if defined $not_a_prime[$factor];   # already known as not a prime
        
        # mark all the multiples of $factor as non-primes (sieve of Eratosthenes)
        $start = int($from / $factor);           # multiples less than $start have already been done
        $start = 2 if $start < 2;
        for ($multiple = $start; $factor * $multiple <= $to; $multiple ++) {
            $not_a_prime[$factor * $multiple] = 1;
        }
    }
    
    # now test the primes in this range for left-truncatability
    TEST: for $test ($from .. $to) {
        
        # remove ineligibles - not prime, is a single digit, contains 0 or ends in 9
        next if (defined $not_a_prime[$test] or $test =~ m|0| or $test =~ m|9$| or $test < 11);
            
        # test for left-truncatability and construct string showing proof
        $this = $test;
        $string = qq[$this];
        
        # remove successive left digits and test the residue for primeness
        while ($this =~ s|\d(\d+)|$1|) {   
            next TEST if $not_a_prime[$this];
            $string .= qq[ > $this];            
        }
        
        # an answer!
        if (length($line) + length($string) > 57) {
            say $line;
            $line = '';
        }
        $line .= qq[$string, ];

        if (++ $count >= $seeking) {
            say substr($line, 0, -2) if $line;
            last RANGE;
        }
    }
}

Output

First 200 left-truncatable prime numbers:
11 > 1, 13 > 3, 17 > 7, 23 > 3, 31 > 1, 37 > 7, 41 > 1, 
43 > 3, 47 > 7, 53 > 3, 61 > 1, 67 > 7, 71 > 1, 73 > 3, 
83 > 3, 97 > 7, 113 > 13 > 3, 131 > 31 > 1, 137 > 37 > 7, 
167 > 67 > 7, 173 > 73 > 3, 197 > 97 > 7, 211 > 11 > 1, 
223 > 23 > 3, 241 > 41 > 1, 271 > 71 > 1, 283 > 83 > 3, 
311 > 11 > 1, 313 > 13 > 3, 317 > 17 > 7, 331 > 31 > 1, 
337 > 37 > 7, 347 > 47 > 7, 353 > 53 > 3, 367 > 67 > 7, 
373 > 73 > 3, 383 > 83 > 3, 397 > 97 > 7, 431 > 31 > 1, 
443 > 43 > 3, 461 > 61 > 1, 467 > 67 > 7, 523 > 23 > 3, 
541 > 41 > 1, 547 > 47 > 7, 571 > 71 > 1, 613 > 13 > 3, 
617 > 17 > 7, 631 > 31 > 1, 641 > 41 > 1, 643 > 43 > 3, 
647 > 47 > 7, 653 > 53 > 3, 661 > 61 > 1, 673 > 73 > 3, 
683 > 83 > 3, 743 > 43 > 3, 761 > 61 > 1, 773 > 73 > 3, 
797 > 97 > 7, 811 > 11 > 1, 823 > 23 > 3, 853 > 53 > 3, 
883 > 83 > 3, 911 > 11 > 1, 937 > 37 > 7, 941 > 41 > 1, 
947 > 47 > 7, 953 > 53 > 3, 967 > 67 > 7, 971 > 71 > 1, 
983 > 83 > 3, 997 > 97 > 7, 1223 > 223 > 23 > 3, 
1283 > 283 > 83 > 3, 1367 > 367 > 67 > 7, 
1373 > 373 > 73 > 3, 1523 > 523 > 23 > 3, 
1571 > 571 > 71 > 1, 1613 > 613 > 13 > 3, 
1811 > 811 > 11 > 1, 1823 > 823 > 23 > 3, 
1997 > 997 > 97 > 7, 2113 > 113 > 13 > 3, 
2131 > 131 > 31 > 1, 2137 > 137 > 37 > 7, 
2311 > 311 > 11 > 1, 2347 > 347 > 47 > 7, 
2383 > 383 > 83 > 3, 2467 > 467 > 67 > 7, 
2617 > 617 > 17 > 7, 2647 > 647 > 47 > 7, 
2683 > 683 > 83 > 3, 2797 > 797 > 97 > 7, 
2953 > 953 > 53 > 3, 2971 > 971 > 71 > 1, 
3137 > 137 > 37 > 7, 3167 > 167 > 67 > 7, 
3271 > 271 > 71 > 1, 3313 > 313 > 13 > 3, 
3331 > 331 > 31 > 1, 3347 > 347 > 47 > 7, 
3373 > 373 > 73 > 3, 3461 > 461 > 61 > 1, 
3467 > 467 > 67 > 7, 3541 > 541 > 41 > 1, 
3547 > 547 > 47 > 7, 3571 > 571 > 71 > 1, 
3613 > 613 > 13 > 3, 3617 > 617 > 17 > 7, 
3631 > 631 > 31 > 1, 3643 > 643 > 43 > 3, 
3673 > 673 > 73 > 3, 3761 > 761 > 61 > 1, 
3797 > 797 > 97 > 7, 3823 > 823 > 23 > 3, 
3853 > 853 > 53 > 3, 3911 > 911 > 11 > 1, 
3947 > 947 > 47 > 7, 3967 > 967 > 67 > 7, 
4211 > 211 > 11 > 1, 4241 > 241 > 41 > 1, 
4271 > 271 > 71 > 1, 4283 > 283 > 83 > 3, 
4337 > 337 > 37 > 7, 4373 > 373 > 73 > 3, 
4397 > 397 > 97 > 7, 4523 > 523 > 23 > 3, 
4547 > 547 > 47 > 7, 4643 > 643 > 43 > 3, 
4673 > 673 > 73 > 3, 4937 > 937 > 37 > 7, 
4967 > 967 > 67 > 7, 5113 > 113 > 13 > 3, 
5167 > 167 > 67 > 7, 5197 > 197 > 97 > 7, 
5347 > 347 > 47 > 7, 5431 > 431 > 31 > 1, 
5443 > 443 > 43 > 3, 5641 > 641 > 41 > 1, 
5647 > 647 > 47 > 7, 5653 > 653 > 53 > 3, 
5683 > 683 > 83 > 3, 5743 > 743 > 43 > 3, 
5953 > 953 > 53 > 3, 6113 > 113 > 13 > 3, 
6131 > 131 > 31 > 1, 6173 > 173 > 73 > 3, 
6197 > 197 > 97 > 7, 6211 > 211 > 11 > 1, 
6271 > 271 > 71 > 1, 6311 > 311 > 11 > 1, 
6317 > 317 > 17 > 7, 6337 > 337 > 37 > 7, 
6353 > 353 > 53 > 3, 6367 > 367 > 67 > 7, 
6373 > 373 > 73 > 3, 6397 > 397 > 97 > 7, 
6547 > 547 > 47 > 7, 6571 > 571 > 71 > 1, 
6653 > 653 > 53 > 3, 6661 > 661 > 61 > 1, 
6673 > 673 > 73 > 3, 6761 > 761 > 61 > 1, 
6823 > 823 > 23 > 3, 6883 > 883 > 83 > 3, 
6911 > 911 > 11 > 1, 6947 > 947 > 47 > 7, 
6967 > 967 > 67 > 7, 6971 > 971 > 71 > 1, 
6983 > 983 > 83 > 3, 6997 > 997 > 97 > 7, 
7211 > 211 > 11 > 1, 7283 > 283 > 83 > 3, 
7331 > 331 > 31 > 1, 7523 > 523 > 23 > 3, 
7541 > 541 > 41 > 1, 7547 > 547 > 47 > 7, 
7643 > 643 > 43 > 3, 7673 > 673 > 73 > 3, 
7823 > 823 > 23 > 3, 7853 > 853 > 53 > 3, 
7883 > 883 > 83 > 3, 7937 > 937 > 37 > 7, 
8167 > 167 > 67 > 7, 8311 > 311 > 11 > 1, 
8317 > 317 > 17 > 7, 8353 > 353 > 53 > 3, 
8431 > 431 > 31 > 1, 8443 > 443 > 43 > 3, 
8461 > 461 > 61 > 1, 8467 > 467 > 67 > 7, 
8641 > 641 > 41 > 1, 8647 > 647 > 47 > 7, 
8761 > 761 > 61 > 1, 8941 > 941 > 41 > 1, 
8971 > 971 > 71 > 1, 9137 > 137 > 37 > 7, 
9173 > 173 > 73 > 3, 9241 > 241 > 41 > 1