Project Euler Problem 36 Solution


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


#!/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   0m3.323s
user   0m3.856s
sys    0m0.260s


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.175s
user   0m0.172s
sys    0m0.000s


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

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

Questions? Comments? Send me an email: [email protected]