--- title: "Project Euler #4: Largest Palindrome Product" author: nbloomf date: 2017-03-08 tags: project-euler, literate-haskell --- First some boilerplate. > module ProjectEuler004 where > > import Data.List > import Data.Maybe > import System.Exit [Problem 4](https://projecteuler.net/problem=4) from Project Euler:
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.
"Palindromeness" is very different from most interesting properties of numbers; it is an artifact of one of many possible *representations* of the number. In this case, the representation in base 10. Let's start by nailing down a definition for "palindrome".
Suppose $A = \sum_{k=0}^{t-1} a_k 10^k$ is a $t$-digit number base 10 (that is, the $a_k$ are integers between 0 and 9 (inclusive) and $a_{t-1}$ is not zero). We say $A$ is a *palindrome* if $a_{t-1-k} = a_k$ for all $0 \leq k < t$.
The first thing I'll do is write helper functions to convert a number to its base 10 digits and back. > -- base 10 digits of n in 'little endian' order > -- (least significant digits first) > toDigits :: Integer -> [Integer] > toDigits n = if n <= 0 > then [] > else (nrem10) : toDigits (nquot10) > > fromDigits :: [Integer] -> Integer > fromDigits = sum . zipWith (*) (map (10^) [0..]) > > numDigits :: Integer -> Integer > numDigits n = sum $map (const 1)$ toDigits n Sanity check: > test_digits :: Integer -> Bool > test_digits n = n == (fromDigits $toDigits n) And a test: haskell$> all test_digits [1..1000000] True  Note that our lists of digits come out "backward"; that is, least significant first. haskell $> toDigits 12345 [5,4,3,2,1]  Then we can detect whether a given number is a palindrome in base 10. > is_palindrome_10 :: Integer -> Bool > is_palindrome_10 n = let ds = toDigits n in > ds == (reverse ds) Now we're not just looking for the largest palindrome of a given length; that would be easy -- the string of all 9s is the largest palindrome with a given number of digits. Instead, we want the largest palindrome that is the product of two 3-digit numbers. The most obvious solution is to list all the products of two 3-digit numbers, filter for the palindromes, and find the max. > -- the triple (a,b,a*b) which yields the largest > -- palindrome product a*b among the pairs of > -- t-digit numbers a and b > pe4' :: Integer -> (Integer, Integer, Integer) > pe4' t = > let > thd (_,_,x) = x > min = 10^(t-1) > max = 10^t - 1 > in > maximumBy (\x y -> compare (thd x) (thd y))$ > filter (is_palindrome_10 . thd) $> [(a,b,a*b) | a <- [min..max], b <- [a..max]] This pe4' works well enough: haskell$> pe4' 1 (3,3,9) $> pe4' 2 (99,91,9009)$> pe4' 3 (993,913,906609) $> pe4' 4 (9901,9999,99000099)  Two observations. First, there appears to be a pattern emerging in these results. Second, unfortunately I can't feasibly explore that pattern further (yet) because as t gets larger, pe4' t gets way slow. It's not hard to see why; pe4' t constructs a list of $$\binom{9 \cdot 10^{t-1}}{2} = \frac{(9 \cdot 10^{t-1})(9 \cdot 10^{t-1} - 1)}{2}$$ candidates to check by brute force. To see if we can find a better way, let's look at the simplest version of this problem: finding the largest palindrome product among products of 1-digit numbers. To this end, consider the multiplication table for 1-digit numbers below. $$\begin{array}{c|ccccccccc} & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ \hline 9 & 81 & 72 & 63 & 54 & 45 & 36 & 27 & 18 & 9 \\ 8 & & 64 & 56 & 48 & 40 & 32 & 24 & 16 & 8 \\ 7 & & & 49 & 42 & 35 & 28 & 21 & 14 & 7 \\ 6 & & & & 36 & 30 & 24 & 18 & 12 & 6 \\ 5 & & & & & 25 & 20 & 15 & 10 & 5 \\ 4 & & & & & & 16 & 12 & 8 & 4 \\ 3 & & & & & & & 9 & 6 & 3 \\ 2 & & & & & & & & 4 & 2 \\ 1 & & & & & & & & & 1 \\ \end{array}$$ The first thing to jump out at me is that the vast majority of these products are *not* palindromes. That's not really surprising I guess -- there are$9 \cdot 10^{2t-1}$different$2t$-digit numbers, but only$9 \cdot 10^{t-1}$of them are palindromes, so to a first approximation the probability that an arbitrary$2t$-digit number is a palindrome is about$10^{-t}$. So maybe instead of searching among the products of$t$-digit numbers for palindromes, it would be faster to search among the palindromes for products of$t$-digit numbers. A Digression on Palindromes --------------------------- The rarity of palindromes highlights a disturbing possibility. The problem of finding the *largest* palindrome product implicitly assumes that at least one palindrome product must exist, but this is not obvious to me. After some experimenting, I am convinced that palindrome products exist among pairs of$t$-digit numbers for any$t$. I got a little distracted thinking about this probem, so I'll just dump the results here. The first result allows us to recognize a family of palindromes constructed from other palindromes. Let$t,u,v \geq 1$be natural numbers, and let$A = \sum_{k=0}^{t-1} a_k 10^k$and$B = \sum_{k=0}^{u-1} b_k 10^k$be$t$- and$u$-digit palindromes, respectively. That is,$a_k = a_{t-1-k}$when$0 \leq k < t$and$b_k = b_{u-1-k}$when$0 \leq k < u$. Then $$M = A + 10^{t+v} B + 10^{t+u+2v} A$$ is a$(2t+u+2v)$-digit palindrome. Note that $$\begin{eqnarray*} M & = & A + 10^{t+v} B + 10^{2t+u+2v} A \\ & = & \sum_{k=0}^{t-1} a_k 10^k + 10^{t+v} \sum_{k=0}^{u-1} b_k 10^k + 10^{2t+u+2v} \sum_{k=0}^{t-1} a_k 10^k \\ & = & \sum_{k=0}^{t-1} a_k 10^k + \sum_{k=0}^{u-1} b_k 10^{t+v+k} + \sum_{k=0}^{t-1} a_k 10^{t+u+2v+k} \\ & = & \sum_{k=0}^{t-1} a_k 10^k + \sum_{k=t+v}^{t+u+v-1} b_{k-t-v} 10^k + \sum_{k=t+u+2v}^{2t+u+2v-1} a_{k-t-u-2v} 10^k \\ & = & \sum_{k=0}^{2t+u+2v-1} e_k 10^k \end{eqnarray*}$$ where $$e_k = \left\{ \begin{array}{ll} a_k & \mathrm{if}\ 0 \leq k < t \\ 0 & \mathrm{if}\ t \leq k < t+v \\ b_{k-t-v} & \mathrm{if}\ t+v \leq k < t+u+v \\ 0 & \mathrm{if}\ t+u+v \leq k < t+u+2v \\ a_{k-t-u-2v} & \mathrm{if}\ t+u+2v \leq k < 2t+u+2v. \end{array} \right.$$ Certainly$M$has$2t+u+2v$digits. To see that$M$is a palindrome, we need to check that $$e_{2t+u+2v-1-k} = e_k$$ for$0 \leq k < 2t+u+2v$. We will break this interval into 5 subintervals. 1. Suppose$0 \leq k < t$. Then$0 \leq t-1-k < t$, and so$t+u+2v \leq 2t+u+2v-1-k < 2t+u+2v$. So $$e_{2t+u+2v-1-k} = a_{2t+u+2v-1-k-t-u-2v} = a_{t-1-k} = a_k = e_k.$$ 2. Suppose$t \leq k < t+v$. Then$0 \leq t+v-1-k < v$, and so$t+u+v \leq 2t+u+2v-1-k < t+u+2v$. So $$e_{2t+u+2v-1-k} = 0 = e_k.$$ 3. Suppose$t+v \leq k < t+u+v$. Then$0 \leq t+u+v-1-k < u$, and so$t+v \leq 2t+u+2v-1-k < t+u+v$. So $$\begin{eqnarray*} e_{2t+u+2v-1-k} & = & b_{2t+u+2v-1-k-t-v} \\ & = & b_{t+u+v-1-k} \\ & = & b_{u-1-t-u-v+1-k} \\ & = & b_{k-t-v} \\ & = & e_{k}. \end{eqnarray*}$$ 4. Suppose$t+u+v \leq k < t+u+2v$. Then$0 \leq t+u+2v-1-k < v$, and so$t \leq 2t+u+2v-1-k < t+v$. So $$e_{2t+u+2v-1-k} = 0 = e_k.$$ 5. Suppose$t+u+2v \leq k < 2t+u+2v$. Then$0 \leq 2t+u+2v-1-k < t$. So $$\begin{eqnarray*} e_{2t+u+2v-1-k} & = & a_{2t+u+2v-1-k} \\ & = & a_{t-1-2t-u-2v+i+k} \\ & = & a_{k+t-u-2v} \\ & = & e_k. \end{eqnarray*}$$ Thus$M$is a$(2t+u+2v)$-digit palindrome. This result lets us recognize *some* palindromes. The next result lets us construct new palindrome products from old ones. Let$A$and$B$be$t$-digit numbers such that both$AB$and$2AB$are$2t$-digit palindromes. Let$v$be a positive integer, and define $$H_v(A) = A(1 + 10^{2t+v})\ \mathrm{and}\ K_v(B) = B(1 + 10^{2t+v}).$$ Then$H_v$and$K_v$are$(3t+v)$-digit numbers and$H_vK_v$is a$(6t+2v)$-digit palindrome. Expanding$H_vK_v$, we have $$H_vK_v = AB + 10^{2t+v}(2AB) + 10^{2t+2t+2v}AB.$$ The previous theorem applies, and$H_vK_v$is a$(6t+2v)$-digit palindrome. Let's make$H_v$and$K_v$executable. > h_ :: Integer -> Integer -> Integer > h_ v a = a * (1 + 10^(2*t+v)) > where t = numDigits a > > k_ :: Integer -> Integer -> Integer > k_ v b = b * (1 + 10^(2*t+v)) > where t = numDigits b And the next result gives us a concrete family of palindrome products with factors of even digit length. Let$t$and$m$be positive natural numbers, and define$Q_{t,m} = \sum_{k=0}^{t-1} 10^{mk}$. Now define $$A_{t,m} = Q_{2t,m},$$ $$B_{t,m} = 1 + 10^{tm}(10^m-1)Q_{t,m},$$ and $$C_t = Q_{t,m}(1 + 10^{3tm}).$$ Then$A_t$is a$(2tm - m + 1)$-digit number, and$B_t$is a$2tm$-digit number, and both$A_tB_t$and$2A_tB_t$are$(4tm - m + 1)$-digit palindromes. Note that$A_{t,m} = Q_{t,m}(1 + 10^{tm})$and $$Q_{t,m} = \frac{10^{tm} - 1}{10^m-1}.$$ Expanding$A_{t,m}B_{t,m}$, then, we have $$A_{t,m}B_{t,m} = Q_{t,m}(1 + 10^{tm})(1 - 10^{tm} + 10^{2tm}) = C_{t,m}$$ as needed. To see the digit counts, note that$Q_{t,m}$has$(tm-m+1)$digits. Note also that all the digits of$C_{t,m}$are 1, so that$2C_{t,m}$is also a palindrome. Let's make$Q_{t,m}$,$A_{t,m}$, and$B_{t,m}$executable. > q_ :: Integer -> Integer -> Integer > q_ t m = sum$ map (\k -> 10^(m*k)) [0..(t-1)] > > a_ :: Integer -> Integer -> Integer > a_ t m = q_ (2*t) m > > b_ :: Integer -> Integer -> Integer > b_ t m = 1 + (10^(t*m))*(10^m - 1)*(q_ t m) > > c_ :: Integer -> Integer -> Integer > c_ t m = (q_ t m)*(1 + 10^(3*t*m)) Sanity check: > test_abc :: Integer -> Integer -> Bool > test_abc t m = > let > a = a_ t m; b = b_ t m; c = c_ t m > in and > [ a*b == c > , (numDigits a) == 2*t*m - m + 1 > , (numDigits b) == 2*t*m > , (numDigits c) == 4*t*m - m + 1 > , is_palindrome_10 c > , is_palindrome_10 (2*c) > ] And a test: haskell $> and [test_abc t m | t <- [1..10], m <- [1..10]] True  This gives an infinite family of palindrome products. Note that if$m = 1$, then both factors have the same number of digits --$2t$-- and the product has$4t$digits. Here are the first 5 examples. --------------------------------------------------$tA_{t,m}B_{t,m}A_{t,m}B_{t,m}$---- ---------- --------- ----------------- 1 11 91 1001 2 1111 9901 11000011 3 111111 999001 111000000111 4 11111111 99990001 1111000000001111 5 1111111111 9999900001 11111000000000011111 -------------------------------------------------- Note that row$k$in this table has factors$A$and$B$with$2k$digits, and the (palindrome) product has$4k$digits. Taking the first row,$A = 11$and$B = 91$, we can use these in our$H_v$and$K_v$, with$v = 1$, we get another family of palindrome products. -----------------------------------------------------------------$vH_v(A_{1,1})K_v(B_{1,1})H_v(A_{1,1})K_v(B_{1,1})$---- --------------- --------------- --------------------------- 1 1100011 9100091 10010200201001 3 110000011 910000091 100100020020001001 5 11000000011 91000000091 1001000002002000001001 7 1100000000011 9100000000091 10010000000200200000001001 ----------------------------------------------------------------- Note that if$v = 2k+1$then this table gives two$(2k+7)$-digit numbers whose (palindrome) product has$4k+14$digits. Along with the observation that$993 \cdot 913 = 906609$and$11011 \cdot 91091 = 1003003001$, we can say the following. Let$k \geq 2$. Then among the$k$-digit numbers, there exists a pair$A$and$B$such that$AB$is a$2k$-digit palindrome. In particular, the largest such palindrome has$2k$digits. Right, because the whole point of this digression was to establish this fact about largest palindrome products. Meanwhile --------- Our alternate strategy for this problem was to search among the palindromes for$k$-digit factorizations; and now we know that it's enough to look among the$2k$-digit palindromes -- we are guaranteed to find a factorization there. This simplifies the search space a bit. So the new strategy is to generate the$2k$-digit palindromes in reverse order and look for the first one that factors are a product of two$k$-digit numbers. > -- the 2k-digit palindromes > palindromes :: Integer -> [Integer] > palindromes k = map (fromDigits . make) (digits k) > where > -- turn a list into a palindrome > make ds = ds ++ reverse ds > > digits :: Integer -> [[Integer]] > digits k = foo k [] > where > foo 0 _ = [[]] > foo k z = do > d <- [9,8,7,6,5,4,3,2,1] ++ z > ds <- foo (k-1)  > return (d:ds) Now given a$2k$-digit palindrome, we want to know whether it factors as a product of two$k$-digit numbers. Note that if$N = AB$, then without loss of generality$A \leq \sqrt{N}$and$\sqrt{N} \leq B$. So it is enough to search for a factorization of$N$where$10^{t-1} \leq A \leq \lfloor \sqrt{N} \rfloor$. Here's a utility function to find$\lfloor \sqrt{N} \rfloor$by bisection. > -- find t such that t^2 <= n < (t+1)^2 > floor_sqrt :: Integer -> Integer > floor_sqrt n = > let > bisect (a,b) = if b-a <= 1 > then a > else let m = (b+a)quot2 in > if m^2 <= n > then bisect (m,b) > else bisect (a,m) > in > if n < 0 > then error "floor_sqrt: negative argument" > else bisect (1,n) Sanity check: > test_floor_sqrt :: Integer -> Bool > test_floor_sqrt n = let q = floor_sqrt n in > (q^2 <= n) && (n < (q+1)^2) And a test: haskell %> all test_floor_sqrt [1..10000] True  Also, if we wish to factor a$2k$-digit number as a product of$k$digit numbers, we should search "down" from$\lfloor \sqrt{N} \rfloor$to$10^{t-1}$rather than the reverse. This is because smaller factors are likely to give quotients with too many digits. > -- search for a factorization of n into t-digit factors > does_factor :: Integer -> Integer -> Maybe (Integer, Integer) > does_factor t n = > let > check m > | m < 10^(t-1) = Nothing > | nremm == 0 = if numDigits (nquotm) == t > then Just m > else check (m-1) > | otherwise = check (m-1) > in > case check (floor_sqrt n) of > Nothing -> Nothing > Just m -> Just (m, nquotm) > > pe4'' :: Integer -> (Integer, Integer, Integer) > pe4'' k = > let > (a,b) = head$ catMaybes $map (does_factor k) (palindromes k) > in (a,b,a*b) This pe4'' is still slow, as we still check an exponential number of cases. But we can squeeze out a couple more values. haskell$> pe4'' 2 (91,99,9009) $> pe4'' 3 (913,993,906609)$> pe4'' 4 (9901,9999,99000099) $> pe4'' 5 (99681,99979,9966006699)  Interesting! It looks like the form of the largest palindrome product depends on whether the factors have an even or odd number of digits. Anyway, the final answer is: > pe4 :: Integer > pe4 = let (_,_,x) = pe4'' 3 in x > > main :: IO () > main = do > let > success = and > [ all test_digits [1..1000000] > , and [ test_abc t m | t <- [1..10], m <- [1..10] ] > , all test_floor_sqrt [1..10000] > ] > if success > then putStrLn$ show pe4 > else exitFailure