TWC 147: Prime without Left, and Pent without Quad

In which we bravely overcome ambiguity, and dodge two approaches in the face of (O³).

TWC Task #1, Truncatable Prime


"Left-truncatable prime" is not fully defined by the task; are leading zeros valid?
e.g. 103 -> 03 -> 3 ; all are prime, but is 03 considered a "number"?

UPDATE:'s Raku Study Group just pointed out that task description does say "contains no 0", so the task was fully defined, and I had no need for the "filter" half of the solutions below. Mea culpa!

OEIS has separate pages for each definition, but both start with:
(2, 3, 5, 7, 13, 17, 23, 37, 43, 47):

A033664 …, 53, 67, 73, 83, 97, 103, 107, 113, …
A024785 …, 53, 67, 73, 83, 97, 113, …

Since one definition is more easily written as a filter, and the other definition is best written as a generator, I wrote both.


My Raku program starts with the "filter" approach:

sub is-left-truncatable-prime ( UInt \N --> Bool ) {
    return (0 ..^ N.chars)          # Start of each substring
        .map(  { N.substr($_) })    # All left-truncated substrings
        .first({ .is-prime.not })   # Find the first non-prime
        .defined.not;               # If no non-primes, then True
constant @LTP_A033664 = grep &is-left-truncatable-prime, ^Inf;

The .first method, combined with the laziness of the .map method, allows an early return without .substr having to generate every single substring. Rephrasing to use .all is only slightly clearer, so I used .first.

The "generator" approach starts with the single digit primes as the first "generation", and pre-pends 1..9 to each element of gen#1 (and filters out non-primes) to create all-double-digit gen#2. Gen#3 will all be triple-digits, and so on.

my @LTP_A024785 = lazy gather loop {
    state @current_gen = grep &is-prime, ^10;
    .take for @current_gen;
    @current_gen = grep &is-prime, ((1..9) X~ @current_gen);

Since each number in a generation has the same number digits, and the first generation is in numeric order, each subsequent (1..9) X~ @current_gen generation will also be in order.

Both arrays are lazy, so they get their elements populated on demand. Final output is just:

put @LTP_A033664.head(20);
put @LTP_A024785.head(20);

2 3 5 7 13 17 23 37 43 47 53 67 73 83 97 103 107 113 137 167
2 3 5 7 13 17 23 37 43 47 53 67 73 83 97 113 137 167 173 197


My Perl program is just a conversion of the Raku, with adaptations to loosely replace the laziness that Perl lacks.

The ntheory (Number Theory) module has is_prime, which saves me much code.

TWC Task #2, Pentagon Numbers


Some obvious problems:

  • Not only do we need to scan all 2-combinations (O²) of a list, we also have to scan the list of pents to find the difference and the sum (O³ and bigger, unless we binary search and/or hash).
  • Unless we pre-build the list to a pre-known limit (which we could only do if we already knew the answer), then at the time that we want to check A+B for presence in the list of pents, the value will not exist in the list yet.
  • We need all 2-combinations, and Raku has a .combinations method that we can invoke with (2), but it will not work with the lazy infinite list that idiomatic for @pents.

If we did already know how big to pre-build the pents, then the solution would be simple:

constant @pents = map { $_ * (3 * $_  -  1) div 2 }, 1..*;
my %p = @pents.head(2400).Set;
say @pents.head(2400).combinations(2).first: {
    %p{  [+] .list } and
    %p{ [R-] .list }

I don't want to do that.

If we "solve" the pent equation of n(3n-1)/2 = P via quadratic formula (a=3,b=-1,c=-2P), we can write a is_pentagon_number sub, which would solve the first two problems!

sub is-pentagon-number ( \p ) {
    my \inner = 24 * p + 1;
    my \near_root = inner.sqrt.round;

    return near_root ** 2 == inner
        && near_root %  6 == 5

This would work perfectly.
I chose not to do that, either.

Instead, let's call the sum of the two pents "A", and the difference "D". Then re-arrange like so:

# Where A,B,C,D are all pentagonal numbers:
# B + C == A      ,  B - C == D     Original problem statement
#     C == A - B  ,  B - C == D     Rearranged as two differences
#     C == A - B  ,  B-(A-B)==D     (C,D), expressed only in A and B

So, if we find any two pentagonal numbers A,B where A-B is pentagonal and B-(A-B) is pentagonal, then we have a solution. The desired numbers will be the inner two: (B,C).

With this reorganization, we will always be "looking backwards" into parts of @pent that have already been generated. The cost will be in generating all the way to A; a solution using is-pentagon-number would only need to generate to B.


My Raku program uses for @pents.kv as a outer loop, and for @pents.head(i) as the inner loop, to replicate the disallowed .combinations(2).

sub find-first-plus-and-minus-pentagon_numbers ( ) {
    constant @pents = map ->\n { n *(3*n - 1) div 2 }, 1..*;

    my %p;
    for @pents.kv -> \i, \A {
        %p{A} = 1;

        for @pents.head(i) -> \B {
            my \D = A - B;
            my \C = B - D;
            return B, C if %p{C} and %p{D};
put find-first-plus-and-minus-pentagon_numbers();

The three body lines of the inner loop could be replace with one line (return B, C if %p{A - B} and %p{B - (A - B)}), and then the whole inner loop could become a return … with first {…} statement, but then I suspect it would "spark joy" in no one.

Aside:'s Raku Study Group just pointed out that the constant line uses a sigil-less n, which means it gets defined as -> \n, which confusingly looks like a newline character. Good point!


My Perl solution needed almost no structural changes from the Raku, because the lazy generation of the pents can just be appended at the same pace as the outer loop.

sub find_first_plus_and_minus_pentagon_numbers ( ) {
    my @pents;
    my %p;
    for ( my $i = 1 ; ; $i++ ) {
        my $A = $i * (3*$i - 1) / 2; # Pentagon number

        for my $B (@pents) {
            my $D = $A - $B;
            my $C = $B - $D;
            return $B, $C if $p{$C} and $p{$D};

        $p{$A} = 1; 
        push @pents, $A;
say join ' ', find_first_plus_and_minus_pentagon_numbers();

Five is right out. -- Monty Python and the Holy Grail

Leave a comment

About Bruce Gray

user-pic "Util" on IRC and PerlMonks. Frequent speaker on Perl and Raku, but infrequent blogger.