Project Euler 34

問題

145は面白い数である. 1! + 4! + 5! = 1 + 24 + 120 = 145となる.

各桁の数の階乗の和が自分自身と一致するような数の和を求めよ.

注: 1! = 1 と 2! = 2 は総和に含めてはならない.
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2034

回答

ある数が階乗の和になっているか否かを判定する関数を作った。

def is_wa_of_kaijo(i,kaijos):
  s = 0
  for j in str(i):
    s+= kaijos[int(j)]
  if i == s:
    return True
  else:
    return False

当該関数を用いて、最大値と考えられる範囲で全数検索を行ったが、とても遅かった。
なお、n>=7で10**n -1 > 9!*nなので、最高でも9!*7までの範囲を検索すれば十分である。

def main():
  MAX = math.factorial(9)*7
  kaijos = [math.factorial(x) for x in range(0,10)]
  ans = 0
  for i in range(3,MAX):
    if is_wa_of_kaijo(i,kaijos):
      ans += i
  print ans

異なるアプローチとして、先に最大7因子の階乗の和セット型オブジェクトを作成し、当該階乗の和セット型オブジェクトに対して全数検索をかけるということを試してみた。検索の母集団が少なくなるため、少なくとも判定部分は高速になるはずである。
なお、階乗の和リストを作成する際にその因子を覚えさせようとしたが、非常に複雑な処理となってしまったため、実装を断念した。
なお、ゼロの階乗は1であるが、最初の時点では、足し算をしない状態のリストの値を保持するため、0としている。

def main2():
  kaijos = [0] + [math.factorial(x) for x in range(1,10)]
  kaijos2 = set(x1+x2 for x1 in kaijos for x2 in kaijos)
  kaijos3 = set(x1+x2 for x1 in kaijos for x2 in kaijos2)
  kaijos4 = set(x1+x2 for x1 in kaijos2 for x2 in kaijos2)
  kaijos7 = set(x1+x2 for x1 in kaijos3 for x2 in kaijos4)
  kaijos[0] = 1
  ans = -3
  for i in kaijos7:
    if is_wa_of_kaijo(i,kaijos):
      ans += i
  print ans

ジェネレータの内包表記を少し増やすバージョンも考えてみた。

def main3():
  kaijos = [0] + [math.factorial(x) for x in range(1,10)]
  kaijos7 = set(x1+x2+x3+x4+x5+x6+x7 for x1 in kaijos for x2 in kaijos for x3 in kaijos for x4 in kaijos for x5 in kaijos for x6 in kaijos for x7 in kaijos)
  kaijos[0] = 1
  print len(kaijos7)
  ans = -3
  for i in kaijos7:
    if is_wa_of_kaijo(i,kaijos):
      ans += i
  #print ans

実行時間
main2() 0.484
main3() 18.011

この実行時間の差が何に起因するのか、のちに調査してみようと思う。