Project Euler Problem 036
http://projecteuler.net/index.php?section=problems&id=36
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2036
585 = 10010010012 (2進) は10進でも2進でも回文数である. 100万未満で10進でも2進でも回文数になるような数の総和を求めよ. (注: 先頭に0を含めて回文にすることは許されない.)
1桁, 2桁, 3桁 .. 6桁、各桁の回文数を作り2進数に変換、それも回文数なら採用する。
import math import datetime def reverse(n): result = 0 while n: result = result * 10 + n % 10 n /= 10 return result def palindromic(length): if length == 1: for i in xrange(10): yield i else: is_odd = length & 0x01 m = length / 2 start = int(math.pow(10, m-1)) stop = start * 10 for i in xrange(start, stop): if is_odd: x = i * start * 100 + reverse(i) for j in xrange(10): yield x + j * start * 10 else: yield i * start * 10 + reverse(i) def itob(n): result = 1 while n: result *= 10 if n & 0x01: result += 1 n >>= 1 result = reverse(result) / 10 return result def euler036(): result = 0 for i in xrange(1, 7): for j in palindromic(i): b = itob(j) if b == reverse(b): result += j print result begin = datetime.datetime.now() euler036() end = datetime.datetime.now() print end - begin
答え: 872187
実行時間: 0.085804秒くらい