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)))))