60 Days of Euler in F# - Problem 36

The Problem

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.)

The Solution

The one is pretty easy. The hardest part, if you can call it that, is turning a number into a string of binary digits.

let rec intToBinary i =
    match i with
    | 0 | 1 -> string i
    | _ ->
        let bit = string (i % 2)
        (intToBinary (i / 2)) + bit

The intToBinary function simply divides the input by 2 over and over again until the value reaches 0 or 1. This final value is the value of the last binary digit. Before each division, we find i % 2 which equals the next digit in the series. Concatenate them all together and you have a string of binary digits.

Now, we can find out if a string is a palindrome.

let isPalindrome n =
    let s = n.ToString()
    let r = System.String.Join("", s |> Seq.rev)
    s = r

The isPalindrome function simply reverses the string and compares it against the input. If they are equal, it's a palindrome.

Now we can solve the problem:

#time
seq { 1..999999 }
|> Seq.filter isPalindrome
|> Seq.filter (fun x -> isPalindrome (intToBinary x))
|> Seq.sum
#time

We generate the sequence 1..999999 and filter out any number that is not a palindrome. Then we convert the resulting numbers to binary strings and filter out any of those that aren't palindromes. The answer is the sum of the resulting sequence.

Other Posts in This Series