Claudio Cherubino's blog Life of a Googler

Project Euler in F# – Problem 36

A number (in general a word) is palindromic when it can be read in the same way from left to right and in the opposite direction, i.e. it is "symmetrical".

According to the definition, a number can be palindromic when written in base10 and not palindromic in base2, but there are some numbers that are palindromic in both bases.

In Project Euler Problem 36 we have to find all these numbers between 1 and 1 million:

The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

To solve this problem we need two helper functions, one to check whether a number is palindromic and another one to convert a number from base10 to base2:

#light
open Microsoft.FSharp.Math

let isPalindromic n =
  let chars = n.ToString().ToCharArray()
  chars = Array.rev chars

let toBinary (n : BigInt) =
  let rec toBinary1 a v =
    match v with
    | 0I -> a
    | _ ->
      let q,r = BigInt.DivMod (v,2I)
      toBinary1 (r.ToString()::a) q
  toBinary1 [] n |> List.reduce_left (^) |> BigInt.Parse

let euler36 = [1I .. 1000000I] |>
              List.filter isPalindromic |>
              List.filter (fun x -> x |> toBinary |> isPalindromic) |>
              List.reduce_left (+)

The first function checks if a number is palindromic by converting it into an array of digits and checking if this array is equal to its reverse one.

Then we have the toBinary function that is based itself on an inner function called (with a lot of originality) toBinary1.

This recursive function uses the list a to store the remainders of the repeated divisions by 2, until the original number is over.

These digits, converted as strings, are joined with ^, the string concatenation operator and eventually the result is converted to a BigInt.

To find the answer to the problem we start with the list of all numbers between 1 and 1 million and take (filter) only the elements which are palindromic in base10.

After this first step, we filter the list again, this time keeping only those numbers that are palindromic when converted to base2.

The last step is the easiest, we only need to sum the numbers left to get the answer to the problem.