Find the sum of the digits in the number 100!

I am working on a Project Euler problem http://projecteuler.net/problem=20.

$n!$ means $n(n - 1)\dots...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!$

The crux of the problem is that, the number is just too big for native data types.

I could just use python / ruby or some language that has native large int types, but a lot of these problems have clever little tricks.

My fist thought was just to mod 10 the answer over and over, but checking wolframalpha.com shows me that would only trim $24$ digits from the $158.$

My second thought is to make a little BCD implementation capable of adding and multiplying.

So I did a little research, I cant figure out any way to make the gamma function ant easier than the factorial...

I have run across things like Stirling's Approximation, but it seem calculating that would require more work than it is worth to make super sized functions.

so my question, I suppose: can this problem be digested in a way to be solved using only arbitrarily small numbers?

There's got to be a better way.

$100!$ is the product of only 100 small numbers, each of which have an easily found prime factorization. By the Fundamental Theorem of Arithmetic (and commutativity), the prime factorization of $100!$ can be found by "grouping up" like primes from each of its factors' prime factorizations. For example, $8! = 2^3 \cdot 7 \cdot 2 \cdot 3 \cdot 5 \cdot 2^2 \cdot 3 \cdot 2 = 2^7 \cdot 3^2 \cdot 5 \cdot 7$.

Each of the prime factors can be expanded as powers of 10, e.g. $a\times 10^2 + b \times 10 + c$.

From there, it should be more or less straightforward to distribute over powers of 10 to find each individual digit. Add, and done.

I'll see if I can't MATLAB an example... but here's an example for $8!$:

$$\begin{align*} 8! &= 2^7 \cdot 3^2 \cdot 5 \cdot 7\\ &= (1\times 10^2 + 2\times 10 + 8) \cdot 9 \cdot (3\times 10 + 5) \\ &= (9 \times 10^2 + 18 \times 10 + 72) \cdot (3\times 10 + 5) \\ &= ((9+1) \times 10^2 + (8+7)\times 10 + 2) \cdot (3\times 10 + 5) \\ &= (1 \times 10^3 + 1\times 10^2 + 5\times 10 + 2) \cdot (3 \times 10 + 5) \\ &= 3 \times 10^4 + 3\times 10^3 + 15 \times 10^2 + 6 \times 10 + \ldots \\ &\ldots 5\times 10^3 + 5\times 10^2 + 25\times 10 + 10). \end{align*}$$

The last step was the distribution of 35 over the previous terms. Now, group like powers by adding. Any time you get a 2-digit multiple of a power of 10, we shift it's digit over to the next higher power of 10.

$$\begin{align*} 8! &= 3\times 10^4 + 9 \times 10^3 + 12\times 10^2 + 12\times 10 \\ &= 3\times 10^4 + 9 \times 10^3 + 13\times 10^2 + 2\times 10 \\ &= 3\times 10^4 + 10 \times 10^3 + 3\times 10^2 + 2\times 10 \\ &= 4\times 10^4 + 3\times 10^2 + 2\times 10 \\ &= 40320. \end{align*} $$

Now, here's where it gets really cool.

Polynomial multiplication can be thought of as vector convolution, which is the same thing as the Cauchy product. The number 40320 is basically just a polynomial in powers of 10. Pretend momentarily that 10 isn't a number, just a symbol like $x$. Then,

$$40320 = 4 (10)^4 + 0 (10)^3 + 3 (10)^2 + 2 (10)^1 + 0 (10)^0.$$

We can write this in vector form as $[ 4\ 0\ 3\ 2\ 0 ]$.

If we want to then multiply it by something else, say $10 \cdot 9 = 9 (10)^1$ to compute $10!$, then we find the discrete convolution/Cauchy product of the two vectors. I'll leave that up to you, given that it has been pointed out that some folks generally frown on too-complete solutions to PE problems.

The comments to this post are noteworthy. Yes, this is exactly an implementation of a BigInt library. Yes, this is exactly the multiplication algorithm.

In my opinion, however, the purpose of PE isn't to train people how to go find libraries to do their job; it's to discover the underlying mathematics. Hopefully, the relations I've mentioned between Cauchy Products, discrete convolutions, and the multiplication algorithm are interesting -- more interesting than finding a language with BigInt support.