Number of digits in n!
The other day I ran across the fact that 23! has 23 digits. That made me wonder how often n! has n digits.
There can only be a finite number of cases, because n! grows faster than 10n for n > 10, and it's reasonable to guess that 23 might be the largest case. Turns out it's not, but it's close. The only cases where n! has n digits are 1, 22, 23, and 24. Once you've found these by brute force, it's not hard to show that they must be the only ones because of the growth rate of n!.
Is there a convenient way to find the number of digits in n! without having to compute n! itself? Sure. For starters, the number of digits in the base 10 representation of a number x is
a log10x a + 1.
where a z a is the floor of z, the largest integer less than or equal to z. The log of the factorial function is easier to compute than the factorial itself because it won't overflow. You're more likely to find a function to compute the log of the gamma function than the log of factorial, and more likely to find software that uses natural logs than logs base 10. So in Python, for example, you could compute the number of digits with this:
from scipy.special import gammalnfrom math import log, floordef digits_in_factorial(n): return floor( gammaln(n+1)/log(10.0) ) + 1
What about a more elementary formula, one that doesn't use the gamma function? If you use Stirling's approximation for factorial and take log of that you should at least get a good approximation. Here it is again in Python:
from math import log, floor, pidef stirling(n): return floor( ((n+0.5)*log(n) - n + 0.5*log(2*pi))/log(10) ) + 1
The code above is exact for every n > 2 as far as I've tested, up to n = 1,000,000. (Note that one million factorial is an extremely large number. It has 5,565,709 digits. And yet we can easily say something about this number, namely how many digits it has!)
The code may break down somewhere because the error in Stirling's approximation or the limitations of floating point arithmetic. Stirling's approximation gets more accurate as n increases, but it's conceivable that a factorial value could be so close to a power of 10 that the approximation error pushes it from one side of the power of 10 to the other. Maybe that's not possible and someone could prove that it's not possible.
You could extend the code above to optionally take another base besides 10.
def digits_in_factorial(n, b=10): return floor( gammaln(n+1)/log(b) ) + 1def stirling(n, b=10): return floor( ((n+0.5)*log(n) - n + 0.5*log(2*pi))/log(b) ) + 1
The code using Stirling's approximation still works for all n > 2, even for b as small as 2. This is slightly surprising since the number of bits in a number is more detailed information than the number of decimal digits.