It’s been a long time since I last try to solve one of Project Euler problems. A few days ago, I noticed a post on Programming Praxis that deals with prime palindrome (a prime number which also happens to read as a palindrome, such as 101). I thought it should be easy to fire up my old code, but apparently none of the Euler problems I solved were about palprime.

As an illustration, problem 4 asks us to find the largest palindrome made from the product of two 3-digit numbers. Here is my solution using Racket: (I know we can write a procedure to check if a number is a palindrome without converting it first to a string, but this does not really impact the performance of the lookup here.)

(define (rev-string str)
  (list->string (reverse (string->list str))))

(define (palindrome? x)
    (equal? (number->string x) (rev-string (number->string x))))

(define (sol-004)
  (apply max
         (for*/list ([a (in-range 999 100 -1)]
                     [b (in-range a 100 -1)]
                     #:when (palindrome? (* a b)))
           (* a b))))

(sol-004)

So yesterday I wrote a quick script to list all prime palindromes, but it is quite inefficient. First, we could use Racket builtin math procedure more efficiently. For instance, (next-primes z n) returns a list of the next n primes larger than z, from which we could filter out palindrome numbers I guess. But read on the solution proposed on Programming Praxis and you will learn that there’s even a clever way to find the 100th prime palindrome. Anyway, here’s my quick and dirty Racket script from yesterday:

#lang racket

(require math/number-theory)

(define (rev-string str)
  (list->string (reverse (string->list str))))

(define (palindrome? x)
    (equal? (number->string x) (rev-string (number->string x))))

(for ([x (in-range 1 1e6)])
     (when (and (palindrome? x) (prime? x))
       (display (format "~a " x))))

Unless you wrap the above code in an nth form, you can run this in your terminal as follows:

~ % racket palindromic-primes.rkt | cut -d " " -f 100
94049