Project Euler 34

problem

145 is an interesting number. 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of the numbers so that the sum of the factorials of each digit matches itself.

Note: 1! = 1 and 2! = 2 must not be included in the sum. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2034

Answer

I made a function to determine whether a number is the sum of factorials.

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

Using this function, we performed an 100% search within the range considered to be the maximum value, but it was very slow. Since n> = 7 and 10 ** n -1> 9! * N, it is sufficient to search the range up to 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

As a different approach, I first created a factorial sum set type object of up to 7 factors, and tried to perform an 100% search on the factorial sum set type object. At least the decision part should be faster because the search population is smaller. I tried to remember the factors when creating the factorial sum list, but I gave up the implementation because it became a very complicated process. The factorial of zero is 1, but at the beginning, it is set to 0 in order to retain the value of the list without addition.

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

I also considered a version that slightly increases the inclusion notation of the generator.

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

Execution time main2() 0.484 main3() 18.011

I will investigate later what is the cause of this difference in execution time.