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.
First of all, we need a function to verify if a number is palindrome.
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
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.
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.
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.
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
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.