Project Euler – Problem 36 Solution

Problem

The decimal number, 585 = 1001001001₂ (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.)

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 isPalindromic function here is an enhanced version of the one I first wrote for the problem 4 solution, with the added functionality to check if the number is palindromic in the specified base. Using the overloaded Convert.ToString method I was able to easily convert a given number to its binary representation and check if the number is palindromic in base 2.

If you aren’t familiar with functional languages like F#, you might also be curious as to how the isPalindromicBase10 and isPalindromicBase2 functions work. This is a form of function currying where you can create new functions by apply a subset of the required parameters to a base function, see here for more information and examples of this.