【Project Euler】Problem 36: 10進数と2進数で回文数

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 36： 10進数と2進数で回文数

原文 Problem 36: Double-base palindromes

問題の要約：$N<10^6$で10進数と2進数両方で回文数になる$N$の合計を求めよ

回文数のチェックは「【Project Euler】Problem 4: 回文数になる積」で作った関数isPalindを使って作ると以下のようになります。

ans = 0
for n in range(1,10**6):
  if isPalind(str(n)) and isPalind(str(bin(n))[2:]):    
    ans += n

print(f"Answer is {ans}")

これでも問題ないですが、10進数の回文数を作って2進数の回文チェックを行えばループをN=1000まで減らせます。回文数生成関数makePalindsです。1つの数に対して偶数と奇数の2個の回文数を生成します。

def makePalinds(n):
  ns = str(n)
  return int(ns+ns[::-1]), n if len(ns) <= 1 else int(ns+ns[-2::-1])

for i in [1, 23, 450]:
  print(makePalind(i))
# (11, 1)
# (2332, 232)
# (450054, 45054)

これを使って書くと以下のようになります。同じ答えがでるはずです。

ans = 0
for i in range(1,1000):
  for dp in makePalinds(i):
    if isPalind(str(bin(dp))[2:] ):
      ans += dp

print(f"Answer is {ans}")