4
\$\begingroup\$

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))
\$\endgroup\$

3 Answers 3

3
\$\begingroup\$

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

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Bit odd to say "don't reinvent math.factorial" and then reinvent functools.lru_cache :-P \$\endgroup\$
    – Manuel
    Mar 11, 2021 at 6:40
  • \$\begingroup\$ @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). \$\endgroup\$
    – Graipher
    Mar 11, 2021 at 7:28
  • \$\begingroup\$ Your "list_comprehension" solution doesn't have a list comprehension. \$\endgroup\$ Dec 25, 2021 at 16:46
  • \$\begingroup\$ @KellyBundle You are right, it is actually a generator expression... \$\endgroup\$
    – Graipher
    Dec 26, 2021 at 7:41
1
\$\begingroup\$

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()
\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$
    – Graipher
    Mar 11, 2021 at 6:11
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Manuel
    Mar 11, 2021 at 6:24
  • \$\begingroup\$ I will test it later and then I'll see. \$\endgroup\$
    – Graipher
    Mar 11, 2021 at 7:30
  • 1
    \$\begingroup\$ You are right: i.stack.imgur.com/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. \$\endgroup\$
    – Graipher
    Mar 11, 2021 at 7:53
  • \$\begingroup\$ 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. \$\endgroup\$
    – Manuel
    Mar 11, 2021 at 11:48
0
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Actually, 100! ends with 24 zeros. Interesting idea, though benchmarks would be good to see whether / how much faster these are / make it. \$\endgroup\$
    – Manuel
    Mar 11, 2021 at 21:17
  • \$\begingroup\$ I didn't count - I just reckoned 25 from 5,10,15,... and 4 more from 25,50,75,100. Ah, I see what I did - that first batch is only 20 elements! \$\endgroup\$ Mar 11, 2021 at 21:49