Project Euler – 問題36

10進数の585は2進数で1001001001であり、どちらも回文になっている。

1000000未満の数で10進表記でも2進表記でも回文になっているものの和を求め よ。

回文の判定には先頭の0は含めないことに注意せよ。

2進表記の場合、各桁の数は1か0しか存在しないので少なくとも1の位は1でない と回文にならないことがわかる。よって対象となる数は奇数のみである。そこ で100万未満の全ての奇数についてfilterで回文になるものを取り出し和を求め る。回文の判定はreverseしたリストが元のリストと同じものかで行う。2進数 への変換は問題34で定義したintToListと同じ要領で定義する。

intToBinary n = reverse $ i' n
    where i' n
              | n >= 2   = let (d, m) = divMod n 2
                           in m : i' d
              | otherwise = [n]

isPalindrome l = reverse l == l

euler036 = sum $ filter both [1,3..999999]
    where both n = (isPalindrome $ intToList n)
                   && (isPalindrome $ intToBinary n)