I was coding a function for calculating the factorial of a big number in $C$. Since I'm using a structure where I don´t know directly the value of the number, I need to find the number of digits of the result (or a decent upper bound) only knowing the number of digits of my original number. Any help is appreciated, thanks.
Is there a good upper ground to the number of digits of a factorial n! when I only know the number of digits of $n$
factorial
Related Solutions
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.
Suppose first that $n$ is even, say $n=2m$. Then
$$n!=\underbrace{(2m)(2m-1)\ldots(m+1)}_{m\text{ factors}}m!\ge(2m)(2m-1)\ldots(m+1)>m^m=\left(\frac{n}2\right)^{n/2}\;.$$
Now suppose that $n=2m+1$. Then
$$n!=\underbrace{(2m+1)(2m)\ldots(m+1)}_{m+1\text{ factors}}m!\ge(m+1)^{m+1}>\left(\frac{n}2\right)^{n/2}\;.$$
Best Answer
Given a natural number $n$, the number of decimal digits is equal to $d(n)=\lfloor \log_{10}(n)\rfloor +1$. If you only know the value of $d(n)$, then $n$ could be as large as the number consisting of $d(n)$ nines $999...9$, or $10^{d(n)}-1$. This means that the best upper bound we can get on the number of digits of $n!$ given only the number of digits of $n$ is equal to $$d(n!)\le d\big((10^{d(n)}-1)!\big)$$ and this is a tight bound. Let’s see if we can simplify this a bit to get an upper bound that is easier to calculate but a little bit less tight. First of all, note that $d(n) < \log_{10}(n)+1$, so we have $$d(n!)\le \log_{10}\big((10^{d(n)}-1)!\big)+1$$ Now, a companion to Stirling’s Formula tells us that $N!$ is less than or equal to $N^{N+1/2}e^{1-N}$ for all natural numbers $N$. Thus, we have from the above inequality that $$d(n!)\le \frac{10^{d(n)}-1/2}{\ln(10)}\ln(10^{d(n)}-1)+\frac{2-10^{d(n)}}{\ln(10)}+1$$ This is decent, but it’s still a bit ugly. Let’s cut out some unnecessary terms (while preserving inequality) to get the following nicer (but still less tight) upper bound: $$d(n!)\le d(n)\cdot 10^{d(n)}-\frac{10^{d(n)}}{\ln(10)}$$ This formula should work for $n\ge 4$, say.