I love palindromes.

My favorite:

A man, a plan, a canal: Panama

Today’s problem deals with “palindromic numbers” which, I admit, is a concept I never considered before I tried to solve this problem.

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 × 99.

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

F# Solution

First, we need to find out if a number is, in fact, “palindromic”.

let isPalindrome i =
    let chars = string(i)

    let rec palindrome l r =
        if l > r then
            true
        else
            chars.[l] = chars.[r] && palindrome (l+1) (r-1)

    palindrome 0 (chars.Length-1)

The function above converts i to a string and then starts looking at the characters at either end. If they’re the same, it recurses, moving inward, and looks at the next pair of characters. Eventually the counter parameters, l and r cross, at which point we know we have a palindrome.

Next, we need to check the products of all 3-digit numbers to see which are palindromes.

let generator (n1,n2) =
    if (n1 > 999) then None
    else Some(n1*n2,if (n2 = 999) then n1+1,100 else n1,n2+1)

We can pass the above generator function to Seq.unfold to generate a sequence of products of 3-digit numbers. The accumulator value is a tuple containing the two 3-digit numbers to multiply. Each iteration generates the product and increments the accumulator.

Finally, we can put it all together to get the answer:

Seq.unfold generator (100,100)
|> Seq.filter isPalindrome
|> Seq.max