Project Euler # 20 factorial digit sum in Python

Question

n! means n ×ばつ (n − 1) ×ばつ ... ×ばつ 3 ×ばつ 2 ×ばつ 1

For example, 10! = 10 ×ばつ 9 ×ばつ ... ×ばつ 3 ×ばつかける 2 ×ばつかける 1 =わ 3628800, and the sum of the digits in the number 10! is 3 +たす 6 +たす 2 +たす 8 +たす 8 +たす 0 +たす 0 =わ 27. Find the sum of the digits in the number 100!

def fact(n):
 """returns factorial of n."""
 if n <= 1:
 return 1
 return n * fact(n - 1)
def count_digits(n):
 """Assumes n > 1.
 returns sum of digits of n's factorial."""
 factorial = fact(n)
 total = 0
 for digit in str(factorial):
 total += int(digit)
 return total
if __name__ == '__main__':
 print(count_digits(100))

Answer 1

The standardlibrary module math already contains a factorial function. On my machine it is about 20 times faster than your function using n = 100. It also does not suffer from stack size limitations as yours does (try computing fact(3000)).

Alternatively you could learn about memoizing, which will help you in many Project Euler problems. Here it would be useful if you had to evaluate the factorial of many numbers (and even better if the numbers are increasing).

from functools import wraps
def memoize(func):
 cache = func.__cache = {}
 @wraps(func)
 def wrapper(*args, **kwargs):
 key = args, frozenset(kwargs.items())
 if key in cache:
 ret = cache[key]
 else:
 ret = cache[key] = func(*args, **kwargs)
 return ret
 return wrapper
@memoize
def fact(n):
 ...

Note that this decorator only works if your arguments are hashable (so no lists for example).

---

Since getting the sum of the digits of a number is something you will regularly need for Project Euler problems, you should make it a function on its own, which you put in a utils module, to be reused later:

def digit_sum(n):
 """Return the sum of the digits of `n`"""
 return sum(map(int, str(n)))

This will also be faster than your manual for loop or a list comprehension. Not by much, but it is measurable for very large numbers:

def digit_sum_list_comprehension(n):
 return sum(int(x) for x in str(n))
def digit_sum_for(n):
 total = 0
 for digit in str(n):
 total += int(digit)
 return total

enter image description here

• Manuel: Bit odd to say "don't reinvent math.factorial" and then reinvent functools.lru_cache :-P
• Graipher: @Manuel You are absolutely right. But in my excuse, I was still stuck having to use Python 2 at the time, which does not have lru_cache, as it was only introduced in Python 3.2 (albeit in 2011).
• Kelly Bundy: Your "list_comprehension" solution doesn't have a list comprehension.
• Graipher: @KellyBundle You are right, it is actually a generator expression...

Answer 2

For even more speed than Graipher's solution, we can count the digits and multiply instead of turning every single one into an int:

def digit_sum_count(n):
 count = str(n).count
 return sum(i * count(str(i)) for i in range(1, 10))

Benchmark with Graipher's three versions and mine on n=3333! (which has 10297 digits):

2.75 ms 2.75 ms 2.73 ms digit_sum
3.22 ms 3.18 ms 3.20 ms digit_sum_list_comprehension
3.31 ms 3.31 ms 3.32 ms digit_sum_for
1.73 ms 1.72 ms 1.74 ms digit_sum_count

Benchmark code:

from timeit import repeat
from math import factorial
def digit_sum(n):
 return sum(map(int, str(n)))
def digit_sum_list_comprehension(n):
 return sum(int(x) for x in str(n))
def digit_sum_for(n):
 total = 0
 for digit in str(n):
 total += int(digit)
 return total
def digit_sum_count(n):
 count = str(n).count
 return sum(i * count(str(i)) for i in range(1, 10))
funcs = [
 digit_sum,
 digit_sum_list_comprehension,
 digit_sum_for,
 digit_sum_count,
]
n = factorial(3333)
print(len(str(n)))
number = 10
# Correctness
expect = funcs[0](n)
for func in funcs:
 print(func(n) == expect, func.__name__)
print()
# Speed
tss = [[] for _ in funcs]
for _ in range(3):
 for func, ts in zip(funcs, tss):
 t = min(repeat(lambda: func(n), number=number)) / number
 ts.append(t)
 print(*('%.2f ms ' % (t * 1e3) for t in ts), func.__name__)
 print()

• Graipher: Now I would be curious to see how using a collections.Counter would fare, since it only needs one pass on the string instead of ten. Would also be interesting to see when, if ever, your approach becomes slower than mine.
• Manuel: @Graipher You mean you'd like to see whether Counter would slow it down so much that it'd be slower than yours? And I guess if you make n small enough, yours might eventually be faster. Oh and I'm not doing ten passes, I'm doing nine.
• Graipher: I will test it later and then I'll see.
• Graipher: You are right: i.sstatic.net/fCjMT.png This is with the str(n) taken out and directly passing a string to the functions, since at ~10^5 digits that seems to start dominating the results.
• Manuel: Thanks for plotting. Btw I also tried mine with count = str(n).replace('0', '').count. That's another pass, but for n=3333!, about 17% of the digits are zeros and thus the nine counting passes have 17% less to do. But it was slightly slower.

Answer 3

100! ends with 24 zeros. You can save carrying those around unnecessarily. With a bit of thought, we don't need to remove them every iteration, because zeros only appear when we multiply by a number containing 5 in its factorisation:

def factorial_no_trailing_0s(n):
 """Factorial of n, with trailing zeros removed."""
 fact = 1
 for i in range(2, n+1):
 fact *= i
 if i % 5 == 0:
 while fact % 10 == 0:
 fact //= 10
 return fact

or, probably more efficient (but I haven't benchmarked):

def factorial_no_trailing_0s(n):
 """Factorial of n, with trailing zeros removed."""
 fact = 1
 for i in range(2, n+1):
 while i % 5 == 0:
 i //= 5
 fact //= 2
 fact *= i
 return fact