Project Euler Problem 4 in F#

1 minute read

Project Euler problem number 4 asks the following:

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 follows my solution:

open System

let rec is_palindromic (a:string) =
    let length = a.Length;
    match a with
        | ""  -> true
        | x -> match length with
                 | 1 -> true
                 | _ -> x.[0] = x.[length-1] && 
                       is_palindromic (x.Substring(1,(length - 2)))
                 
let max_palindrome =
    let numbers = seq {
        for i in 100 .. 999 do
            for j in 100 .. 999 do
                if is_palindromic(Convert.ToString(i*j)) then yield (i*j) }
    Seq.max numbers

A few considerations:

  • I first define a general recursive function to determine whether a given string is a palindrome.

    I basically check the first and last characters of the string; if they are the same I continue with the second and second last, and so on until I either found a pair of chars that do not match or there's only one char or none left.

    Alternatively, I could have reversed the string and compared the original and reversed strings for equality; however that would have been not just more work than actually needed by the algorithm, but less useful as an excercise in learning F#.

  • The actual algorithm uses brute force to test for palindromicity (neologism?) all the numbers that can be composed multiplying together 3 digits numbers (those from 100 to 999), picking the highest one. Again, as in a previous problem, I am using comprehension to generate a list of candidates.

Updated:

Leave a Comment