My code gives Key error beyond a limit

Question

I was solving Project Euler problem 34

My code gives is as follows:

import functools

limit = int(input())

factDict = { 0:1, 1:1, 2:2, 3:6, 4:24, 5:120, 6:720, 7:5040, 8:40320, 9:362880 }

for i in range(10, limit):
    listNum = list(map(int, list(str(i))))
    #print(listNum)
    sumFact = functools.reduce(lambda x, y: factDict[x] + factDict[y], listNum)
    if(sumFact%i == 0):
        print(i)

It works fine until 140 and then gives:

Traceback (most recent call last):
  File "solution.py", line 10, in <module>
    sumFact=functools.reduce(lambda x, y: factDict[x]+factDict[y], listNum)
  File "solution.py", line 10, in <lambda>
    sumFact=functools.reduce(lambda x, y: factDict[x]+factDict[y], listNum)
KeyError: 25

I printed the list too and found there is no problem there.

Where am I going wrong?

Answer 1

You're not using functools.reduce() correctly.

This: functools.reduce(lambda x, y: factDict[x] + factDict[y], listNum) applied to [1, 4, 0] will (try to) calculate:

factDict[factDict[1] + factDict[4]] + factDict[0]

resulting in this index error (factDict[1] + factDict[4] being equal to 25).

According to the doc:

The left argument, x, is the accumulated value

So if you use factDict[x] you will replace the accumulated value by its factorial (not what you want).

So you have to leave x 'alone'.

Then, to initialize to something "neutral", you can just use 0, this way, it will actually compute (for 140): 0 + factDict[1] + factDict[4] + factDict[0]

So finally:

#!/usr/bin/env python3

import functools

limit = int(input())

factDict = { 0:1, 1:1, 2:2, 3:6, 4:24, 5:120, 6:720, 7:5040, 8:40320, 9:362880 }

for i in range(10, limit):
    listNum = list(map(int, list(str(i))))
    #print(listNum)
    sumFact = functools.reduce(lambda x, y: x + factDict[y], listNum, 0)
    if(sumFact == i):
        print("Found: " + str(i))

Moreover I changed the last test in sumFact == i since you're looking for numbers equal to the sum of their factorials, not being a divisor of the sum of their factorials. (As stated in the comments, you can use the test you like).

PS this doesn't give a lot of results:

$ ./test_script.py
1000000
Found: 145
Found: 40585