Peter
Peter Campbell Smith

Palindromic primes
and moody numbers

Weekly challenge 164 — 9 May 2022

Week 164: 9 May 2022

Task 1

Task — Prime palindrome

Write a script to find all prime numbers less than 1000 which are also palindromes in base 10. Palindromic numbers are numbers whose digits are the same in reverse.

Examples


Example 1:
313 is a palindromic prime, but 337 is not, even though 
733 (337 reversed) is also prime.

Analysis

As this is a simple task it seems fairer to generate the primes rather than using an imported module.

So let's loop over 2 to 1000, discarding anything that's divisible by a prime we've already found, which leaves us with a new found prime.

And now we have to reverse its digits and see whether the forward and reverse versions are the same. There are various ways to reverse the digits, but a simple one-liner like

$reverse = $reverse . $1 while $j =~ m|(.)|g;

seems to do the trick quickly enough.

It's interesting that the last of the 20 primes less than 1000 is 929 and then there isn't another one until 10301. So there are no 4-digit palindromic primes, and I'm sure some clever person will tell us why.

Postscript on 07.10.2024

James Marquis is clearly a clever person and pointed me to this:

Any 4-digit palindrome xyyx can be expressed as 
          1000x + 100y + 10y + x
so that's 1001x + 110y
which is  11.91.x + 11.2.5.y

So any 4-digit palindrome is divisible by 11 and is therefore not prime.

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2022-05-09
# PWC 164 task 1

use v5.28;
use strict;
use warnings;
use utf8;

my (%primes, $j, $p, $results, $reverse);

# discover primes
%primes = ();
OUTER: for $j (2 ... 1000) {
    
    # not prime if $j divisible by a lesser prime
    for $p (keys %primes) {
        next OUTER if $j % $p == 0;
    }
    
    # found a prime, check for palindromicity
    $primes{$j} = 1;
    $reverse = '';
    $reverse = $reverse . $1 while $j =~ m|(.)|g;
    $results .= qq[$j, ] if $j == reverse($j);
}
say qq[\nThe following are palindromic primes:\n] . substr($results, 0, -2);

Output


The following are palindromic primes:
2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373,
383, 727, 757, 787, 797, 919, 929

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain