Project Euler Problem 4

Ivar Thorson bio photo By Ivar Thorson

As usual, we begin with a link to the problem.

This one felt easy compared with the previous problem. Here was my first try:

;; Brute force, counts down. 
(use '[clojure.contrib.math :only (expt sqrt)])

(defn palindromic? [n]
  (= (seq (str n)) (reverse (str n))))

(defn combinations-between [bot top]
  (for [a (reverse (range bot top))
        b (reverse (range a   top))]
    (list a b)))

(apply max (filter palindromic? (map #(apply * %)
                                     (combinations-between 100 1000))))

Not beautiful, but it works. I’m not interested in delving into the problem structure of palindromic numbers here to optimize when the search can actually be stopped. You may notice the reverse’s that indicate I initially thought that trying combinations with decreasing magnitude would guarantee the largest palindromic number was found first, but this turned out to be not true.

Looking at other solutions, I wonder if indeed the more efficient approach is to generate the palindromes first, then look for factors? That way, we turn a problem we don’t know much about (palindromic number theory) into one we do (factorization).

Maybe I’ll try again another day.