September 7, 2008

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Here is my solution in Common Lisp:

(defun 3-digit-divisors (num)
(do ((i (isqrt num) (- i 1)))
((or (and (zerop (mod num i))
(= 3 (length (write-to-string i))
(length (write-to-string (/ num i)))))
(eq i 99))
(cond ((= i 99) nil)
(t (list i (/ num i)))))))

(defun palindrome? (num)
(let ((x (write-to-string num)))
(if (equalp x (reverse x))

(defun problem-4 ()
(do ((i 998899 (- i 1)))
((or (and (palindrome? i)
(3-digit-divisors i))
(< i 1))
(list i (3-digit-divisors i)))))

2-digit-divisors takes a number and returns a list of its largest three-digit divisors if it has any or nil. palindrom? tests to see if a number is a palindrome by comparing the number to the reverse of the number. The solution is calculated by starting with the largest six digit palindrome and testing for the conditions.

Of course, problem-4 can be tweaked for better performance by looping for every palindrome rather than decrementing by one.