Project Euler — Problem 36 Solution

Problem

The dec­i­mal num­ber, 585 = 10010010012 (bina­ry), is palin­dromic in both bases.

Find the sum of all num­bers, less than one mil­lion, which are palin­dromic in base 10 and base 2.

(Please note that the palin­dromic num­ber, in either base, may not include lead­ing zeros.)

Solution

open System
open System.Linq

// checks if the number n is palindromic in the supplied base b
let isPalindromic (b:int) (n:int) =
    let charArray = Convert.ToString(n, b).ToCharArray()
    let revCharArray = Array.rev charArray
    charArray.SequenceEqual(revCharArray)

// using function currying to build two higher-order functions to check
// if number is palindormic in base 10 and base 2 separately
let isPalindromicBase10 = isPalindromic 10
let isPalindromicBase2 = isPalindromic 2

let answer =
    [1..1000000]
    |> List.filter (fun n -> isPalindromicBase10 n && isPalindromicBase2 n)
    |> List.sum

The isPalin­dromic func­tion here is an enhanced ver­sion of the one I first wrote for the prob­lem 4 solu­tion, with the added func­tion­al­i­ty to check if the num­ber is palin­dromic in the spec­i­fied base. Using the over­loaded Convert.ToString method I was able to eas­i­ly con­vert a giv­en num­ber to its bina­ry rep­re­sen­ta­tion and check if the num­ber is palin­dromic in base 2.

If you aren’t famil­iar with func­tion­al lan­guages like F#, you might also be curi­ous as to how the isPalindromicBase10 and isPalindromicBase2 func­tions work. This is a form of func­tion cur­ry­ing where you can cre­ate new func­tions by apply a sub­set of the required para­me­ters to a base func­tion, see here for more infor­ma­tion and exam­ples of this.