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.

Peter's blog post is pure information and fun. Highly recommended.

#!/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;
        }
    }
}

31 lines of code

Output from script

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