## Prime Palindromes

### October 26, 2021

Today’s exercise is from a beginner programming web site:

A prime number, such as 127, has no factors other than itself and one. A palindrome, such as 121, is the same number when its digits are reversed. A prime palindrome, such as 131, is both prime and a palindrome. Find the 100th prime palindrome.

Your task is to write a program to find the 100th prime palindrome; answer the question as if you were explaining the task to a beginner programmer. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

No solution, I just feel compelled to mention Belphegor’s Prime, 1000000000000066600000000000001. A few years ago I played with numbers like this, and if I remember correctly, it’s not hard to construct primes of the form 1000…0something000…01 in any base. It’s a lucky coincidence that we attach numerological significance to 666, 13 (the number of consecutive zeros), and 31 (the total number of digits).

https://en.wikipedia.org/wiki/Belphegor%27s_prime

We discussed Belphegor’s Prime a long time ago.

It is always worth trying the most obvious approach first. If it does not work, you may be able to tweak it to discover why it doesn’t, maybe get some insight into the problem space. For this problem, there are three issues: “prime”, “palindrome”, and “100th”. There is no obvious way of enumerating palindromic integers, but my personal library for Project Euler does include an #isPalindrome method for testing whether a natural number is a palindrome, and of course I have a method for enumerating primes. So the code goes like this:

k := 100.

Integer primesUpTo: 100000000 do: [:p |

(p isPalindrome and: [(k := k – 1) isZero]) ifTrue: [

Transcript print: p; cr.

^true]].

Transcript nextPutAll: ‘Failed.’; cr.

^false

The output is

94049

which is certainly a palindromic prime.

In Haskell this would look much prettier:

(filter isPalindrome primes) !! (100-1)

where filter and !! are built in, primes can be found in many books, and only isPalindrome is tricky.

Again, the obvious way to test whether an integer is a palindrome is to reverse its digits and see if you get the same number again. You could stop early, but let’s stick with an obvious approach.

Integer

methods for: ‘digits’

reverseDigits

|n r|

n := self abs.

r := 0.

[0 < n] whileTrue: [

r := r * 10 + (n \ 10).

n := n // 10].

^self negative ifTrue: [r negated] ifFalse: [r]

Squeak Smalltalk has #primesUpTo:do: but not #isPalindrome. The same is true of Pharo.

Drat. What do I do to preserve indentation?

Note that we need only test palindromes with an odd number of digits since all palindromes with an even number of digits are divisible by 11

@Richard: code tags are what you want here – https://wordpress.com/support/wordpress-editor/blocks/syntax-highlighter-code-block/2/

Here’s an adaptation of some code from an earlier problem that directly generates palindromic sequences of digits 0-9 & checks for primality after a few syntactic checks (doesn’t end in even digit or 5, length is odd). To avoid special cases, start the enumeration from 101 and subtract 5 from target number (there are 5 palindromic primes less than 101). A rather naive prime checker – I tried the modular exponentiation check suggested by Praxis, using essentially the algorithm here, https://en.wikipedia.org/wiki/Modular_exponentiation#Pseudocode, but the squaring step overflowed long before the naive checker lost steam – I’m sure this can be worked around (“Shrage’s algorithm” maybe).

Using 32 bit ints constrains how far we can get (it’s nice that C compilers can now actually check for overflow etc), but 64 bit longs save the day:

BTW, Schrage’s method for doing modular exponentiation without overflow is covered here: https://programmingpraxis.com/2014/01/14/

[…] Came across this on the “Programming Praxis” blog […]

A Mathematica version:

Evaluates to:

94049

Actually, we can implement a suitable modular exponent function very easily, using the (non-standard) 128 bit integer types supported by most compilers & architectures:

This doesn’t speed things up much though, as we spend the majority of the time checking that the numbers that pass the expm test are indeed prime. However, a glance at https://oeis.org/A068445, “Palindromic pseudoprimes (base 2)” shows there aren’t going to be many false positives so we could skip the confirmation (1837381 is the only one in fact, since it doesn’t seem likely our program will get to 127665878878566721 or 1037998220228997301).

This is the assembler output for that modmul function though (gcc 11.2, -O3, on http://godbolt.org):

It’s a little long winded & in fact calls out to a function for the actual mod operation. Let’s see if inline assembler can do better:

A Godbolt shows a more satisfactory result:

but again the effect on runtime is fairly small as it turns out that nearly all the time is in that idiv instruction and the function call overhead is comparatively small.

See https://stackoverflow.com/questions/32540740/intrinsics-for-128-multiplication-and-division for more details, and why there aren’t 128 division intrinsics (which would be a better choice if available). Also, my inline assembler should probably indicate the condition code register may be clobbered:

And it would seem, if anyone cares, that 9223372002002733229 is the largest palindromic prime less than 2^63.

Answer is 94949