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
⌊ log10 x ⌋ + 1.
where ⌊ z ⌋ 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 gammaln from math import log, floor def 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, pi def 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) ) + 1 def 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.
9 thoughts on “Number of digits in n!”
What about using something like sum(log(arange(n)+1)) to compute log(n!)?
Omer: There are better ways to compute log factorial.
If you are using a compiler with a logarithm, we can just assign a double value to the sum of all logarithms from 1 to n. Then, we can find the floor of that and we are done.
Jonathan: stirling() above is O(1), whereas adding the logs is O(n). The O(n) algorithm may very well be faster for sufficiently small n, though.
Even 1000000! is a large number, it is easy to calculate. It looks like SymPy can compute factorial(1000000) in under a second (about 250 ms on my computer).
However, computing len(str(factorial(1000000))) takes over 9 minutes (factorial(1000000) is itself stored in a binary representation).
Somehow I am not getting the correct answer with the Stirling version.
The gammaln formula works. I am using Excel.
Is there a typo?
This problem appeared in various forms the Problems Section of the Mathematics Magazine in 1964 and 1965. It started with the question when does n! contain n digits? It led to a question about the growth of the number of digits in the base b expansion of n! specifically what is the limit as n becomes infinite of the base b expansion of n! when divided by b to the n. It approaches e.
These are interesting thoughts!
Does anybody know how to solve the equation:
10^x == Gamma[x +1].
x would be the precise figure, that expresses the equality between the factorial function and the decadic logarithm.
Just a quick observation:
10! has 7 digits for a ratio of 0.7
100! has 158 digits for a ratio of 1.58
1,000! has 2,568 digits for a ratio of 2.568
10,000! has 35,660 digits for a ratio of 3.566
100,000! has 456,574 digits for a ratio of 4.56574
1,000,000! has 5,565,709 digits for a ratio of 5.565709
10,000,000! has 65,657,060 digits for a ratio of 6.565706
100,000,000! has 756,570,557 digits for a ratio of 7.56570557
1000000000! has 8,565,705,523 digits for a ratio of 8.565705523
10,000,000,000! has 95,657,055,187 digits for a ratio of 9.5657055187
So, the decimal part of digitsof[ (10^n)! ] / (10^n) appears to be converging to 0.5657055… Does anyone know the significance of this value? If not, I claim it as “Evert’s constant”!