# Project Euler 20 Solution: Factorial digit sum

Problem 20

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!

## Solution

The factorial of 100 is a quite big number. By using Stirling's approximation and the calculation of the length of a number, I proved for Problem 25, it's possible to estimate the number of digits we have to deal with:

$\begin{array}{rl}L(n!) &= \lfloor 1 + \log_{10}(n!)\rfloor\\&\approx \left\lfloor 1+\log_{10}\left(\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\right)\right\rfloor\\&= \left\lfloor 1+\frac{1}{2}\log_{10}\left(2\pi n\right)+n\log_{10}n - n\log_{10}e\right\rfloor\end{array}$

Therefore, the length of the number we're looking for is $$L(100!)\approx 158$$. The smallest number with 158 digits would be a 1 and 157 zeros, the biggest one would have all nine or a sum of digits of $$158\times 9=1422$$, which gives a result search space of $$[1, 1422]$$.

### Number reduced by sum of digit is multiple of 9

A known fact in number theory is, that if you take a positive integer and subtract the sum of its digits from that number, you'll end up with a multiple of 9. This can be extended for a general base as well. Let $$n$$ be a positive integer in base $$b$$ with $$k$$ digits, the number then can be represented as:

$n = \sum\limits_{i=0}^k b^in_i$

Since $$b\equiv 1 \pmod{b-1}$$, we know that $$b^m \equiv 1 \pmod{b-1}$$, for an arbitrary $$m$$ and therefore

$\sum\limits_{i=0}^k b^in_i \equiv \sum\limits_{i=0}^k n_i \pmod{b-1}$

Subtracting the sum of the digits $$\sigma(n)$$ from the right side proofs the statement for a general base $$b$$:

$\sum\limits_{i=0}^k b^in_i - \sum\limits_{i=0}^k n_i = n - \sigma(n) \equiv 0 \pmod{b-1}$

That means that $$100!-\sigma(100!) \equiv 0 \pmod{9}$$ and since the factorial is a product of numbers, including $$3^2=9$$, factorial of 100 under the modul 9 will become 0. This reduces the search space from $$[1, 1422]$$ to $$\{9p\in\mathbb{N} | 1\leq p \leq 158\}$$. So we have 158 remaining numbers, which could be the final solution. But since I don't have another idea to reduce the result space even further, here the one line brute force solution:

### Python Brute force Solution

import math
n = 100
print(sum(map(int, str(math.factorial(n)))))


« Back to problem overview