Project Euler in Haskell #4

Problem Description

Link to Project Euler problem 4

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

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

WARNING Solution ahead. Don’t read more if you want to enjoy the benefits of Project Euler and you haven’t already solved the problem.

Solution

First of all, we need a function to verify if a number is palindrome. With isPalindrome we simply convert the number to a string and compare the string with its reverse.

Note that this function applies not only to numbers but to types that implements the Show typeclass.

isPalindrome    :: Show a => a -> Bool
isPalindrome x  =  x' == reverse x' where x' = show x

The simple solution to the problem uses Haskell list comprehension. We enumerate all the products of two 3-digit numbers, filter the palindromes, and extract the largest one.

solution  :: Integer
solution  =  maximum  [x*y | x <- [100..999], y <- [100..999]
                      , isPalindrome (x*y)]

We can improve this solution, noting that the combination of the same terms is considered two times, e.g. x=123,y=456 and x=456,y=123. We can filter the potential palindromes to only include the products where the first term is more than or equal to the second term.

solution'  :: Integer
solution'  =  maximum  [x*y | x <- [100..999], y <- [100..999]
                       , x >= y
                       , isPalindrome (x*y)]

Moreover, if we express the palindromes as a six terms multi-variable polynomial, after some simplifications we find out that all the palindromes of 6-digit are divisible by 11.

$$ P=100000x+10000y+1000z+100z+10y+x $$ $$ P=100001x+10010y+1100z $$ $$ P=11(9091x+910y+100z) $$

We can filter the potential palindromes to only include the products where at least one of the terms is divisible by 11.

solution''  :: Integer
solution''  =  maximum  [x*y | x <- [100..999], y <- [100..999]
                        , x >= y
                        , x `mod` 11 == 0 || y `mod` 11 == 0
                        , isPalindrome (x*y)]

But, if we want to find an efficient solution, we have to change method. Counting downwards from 999, we can find the solution earlier.

The euler4 function recurses on a list of decreasing numerical terms and, with the current term fixed as the first term, executes an inner recursion using the rest of the list as the source for second terms. The resulting product is verified to find out if it is a palindrome. The result of the inner recursion is compared with the candidate palindrome to choose the largest one.

The euler4 function uses two optimization techniques:

• it exits from the inner recursion when it finds the first palindrome: given that the first term of the product is fixed, it could not find a larger palindrome
• it exits from the outer recursion when the candidate palindrome is larger than the square of the first term: given that the subsequent terms are smaller, it could not find a larger palindrome

euler4               :: (Ord a, Num a) => [a] -> a -> a
euler4 []         p  =  p
euler4 ns@(x:xs)  p  |  x*x < p    =  p
                     |  otherwise  =  euler4 xs $ max p $ maxPalindrome ns
                     where
                       maxPalindrome []        =  0
                       maxPalindrome (x':xs')  |  isPalindrome m  =  m
                                               |  otherwise       =  maxPalindrome xs'
                                               where
                                                 m = x * x'

We find the solution calling euler4 with a list from 999 to 100 and with 0 as the candidate palindrome.

solution'''  :: Integer
solution'''  =  euler4 [999,998..100] 0

Note that euler4 could be used to find the largest palindrome made from the product of number with more than 3-digit, e.g. euler4 [9999,9998..1000] 0.

You can find the Literate Haskell code on GitHub and on Bitbucket.