PWC 164 › Palindromic Primes

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

The first task this week is to list all palindromic primes below 1000. Palindromes are very well known to Weekly Challenge enthusiasts as numbers (or words) that are the same forwards and backwards. Prime numbers should need no introduction.

Prime Sieve

I’m going to jump straight to it. Since the task is simple, I’m not going to use an external library such as Math::Prime::Util, even though that would be quite a bit faster. Instead, I’m going to generate the primes myself, using a Sieve of Eratosthenes. There are faster methods, but you can’t beat Eratosthenes for elegance!

sub primes_under {
    my $limit = shift;
    my @comp; # Composite numbers (non-primes)

    for my $n (2..$limit) {
        next if $comp[$n];
        $comp[$_] = 1 for map { $n * $_ } 2..$limit/$n;
    }

    2, grep { !$comp[$_] } 3..$limit;
}

That will generate primes from 2..$limit, and for our very modest limit of 1000, it’s capable of returning that list several thousand times per second.

Palindromes

Now we just need to find palindromes. TIMTOWTDI, but one method that anyone can code in seconds without (much) fear of screwing it up is { $_ eq scalar reverse $_ }. In other words, simply reverse the string and if it’s equal to the original string, it’s a palindrome.

Returning the entire list of palindromic primes below a limit is then as easy as:

say for grep { $_ eq scalar reverse $_ } primes_under( $LIMIT );

There are certainly optimizations that could be made that are a little better asymptotically, but in the 1-1000 range, the distribution is fairly even.

Complete solutions on GitHub.

Observations

If you run my script with a limit of 10000 instead of 1000, you will get the same output. Is this a bug? A hardcoded value somewhere? No! There really are no palindromic primes between 1000 and 10000. In fact, after 929, the next palindromic prime is 10301. There is a similar gap between 98689 and 1003001, and all other even-numbered digit ranges.

In fact, with a little bit of math, one can show 11 is the only palindromic prime with an even number of digits. Since all palindromic numbers with an even number of digits are divisible by 11, any such number that is greater than 11 would be composite, so it would fail the “prime” part of the palindromic prime test.

Proving all even length palindromic numbers are divisible by 11 is a good exercise for you, gentle reader.

That’s all for this task, but task #2 will be next.