Project Euler Problem 36 Solution

Question

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

Clojure

#!/usr/bin/env clojure
(defn reversed [string]
  (apply str (reverse string)))

(defn palindrome? [string]
  (= string (reversed string)))

(defn palindrome-in-decimal-and-binary? [n]
  (and (palindrome? (Integer/toString n 2))
       (palindrome? (Integer/toString n))))

(println (reduce + (filter palindrome-in-decimal-and-binary? (range 1 1000000))))
$ time clojure palindromic-bases.clj
real   0m4.000s
user   0m9.944s
sys    0m0.252s

Haskell

palindrome :: Eq a => [a] -> Bool
palindrome s = s == reverse s

digits :: Int -> Int -> [Int]
digits _ 0 = []
digits base n = r : digits base q
    where (q, r) = quotRem n base

main :: IO ()
main = print $ sum [n | n <- [1..1000000], all palindrome [digits 10 n, digits 2 n]]
$ ghc -O2 -o double-palindrome double-palindrome.hs
$ time ./double-palindrome
real   0m0.170s
user   0m0.164s
sys    0m0.004s

Ruby

#!/usr/bin/env ruby
class String
  def palindrome?
    self == self.reverse
  end
end

puts (1..1000000).select { |i| i.to_s.palindrome? && i.to_s(2).palindrome? }.reduce(:+)
$ time ruby binary-palindrome.rb
real   0m0.324s
user   0m0.312s
sys    0m0.008s