21
$\begingroup$

I was on Math.Stack Exchange the other day and I found a question that said:

How many zeroes are there in 100! ?

I quickly factored it out and said that there were 24 zeroes. However, that are only the trailing zeroes, as the person who asked the question quickly pointed out. As the days passed no one answered the question. My question is the following: is there a method to figure it out without having to compute the whole answer? I initially thought that it could be solved using many divisibility properties, but I didn't figure anything out.

$\endgroup$
10
  • 9
    $\begingroup$ For 100!, one can, as you say, simply compute it. But if we define $Z(n)$ to be the number of non-trivial zeros in the decimal expansion of $n!$, i.e., ignoring the ones coming from the factors of 5 in $n!$, then I don't see any easy way to compute, or even accurately estimate, $Z(n)$. Is it interesting to ask how, aside from the trivial trailing zeros, the digits of $n!$ are distributed? It's not so hard, I think, to show that the leading digits are Benford distributed, i.e., log uniform. $\endgroup$ Jul 13, 2012 at 2:57
  • 6
    $\begingroup$ Here is a link to a proof that the leading digits of $n!$ satisfy Benford's law : williams.edu/go/math/sjmiller/public_html/BrownClasses/197/… I think Benford also conjectured that the frequency of a given digit in $n!$ tends to $1/10$ when $n \to \infty$, but this is probably out of reach... $\endgroup$ Jul 13, 2012 at 7:55
  • 3
    $\begingroup$ This is sequence oeis.org/A027869 , which has no interesting citations. $\endgroup$ Jul 20, 2012 at 19:10
  • 2
    $\begingroup$ BTW, the Mathematica function Zeroes[n_]:=Count[IntegerDigits[n!,10],0] uses only about 10 seconds on my old laptop to discern that $10^6!$ has exactly 782336 zeroes. So apparently there are some tricks to computing factorials. $\endgroup$ Jul 20, 2012 at 19:10
  • 4
    $\begingroup$ For the "tricks" that GMP uses in computing factorial, see page 105 of gmplib.org/gmp-man-5.0.5.pdf $\endgroup$ Jul 20, 2012 at 20:10

4 Answers 4

7
$\begingroup$

Using well known approximations for the length and number of trailing zeroes of n!, and making the reasonable assumption that the inside zeros appear with frequency $\frac{1}{10}$, we get the following approximation of the total number of zeros, t, in n!:

$t = \lfloor \frac{1}{10}(\frac{\log (2 \Pi n)}{2}+n\log (\frac{n}{e})- \frac{n}{4}+ \log(n)) + \frac{n}{4} - log(n)\rfloor $

Which simplifies to:

$t = \lfloor \frac{n (9 \ln (10)-4)+4 (n-9) \ln (n)+2 \ln(2 \Pi n)}{40 \ln(10)} \rfloor$

This approximation seems to work well for n up to at least 10,000.

100!, with digit length 158, has less inside zeroes, 6, with 24 trailing, than the normal expectation for a total of 30, with t=36.

98! is "zero-perfect", i.e. inside zeroes appear with exactly frequency $1/10$, with actual total zero count 35 and $t = 35$

Other examples of zero-perfect factorials are: 1009!, 1097!, 1112!, 2993!, 6128!, ....

There appears to be a strong correlation of n having only 0-3 prime factors in {2, 3, 5} if n! is zero-perfect. Uneven n is often a prime number if n! is zero-perfect.

$\endgroup$
7
  • $\begingroup$ Note that certain numbers have predictableffects. 100! has 2 'more zeros than 99!, which in turn is likely to "kill off" many zeros present in 98!. Can you give a theorem which says how the number of zeros in x and in 99 times x are related? Gerhard "Ask Me About System Design" Paseman, 2012.07.20 $\endgroup$ Jul 21, 2012 at 3:47
  • $\begingroup$ @HalfdanFaber where did you get this, please answer, that some nice solution(i mean WOW! just want to know HOW?).+1, icannot vote more or i could have made +100.Waiting for reply. $\endgroup$
    – Shobhit
    Aug 27, 2013 at 22:31
  • $\begingroup$ Thanks, @sShobhit. You give me too much credit, though. As you can see, I have just taken a known estimate for the total length, subtracted from this a known estimate for the number of trailing zeros, multiplied this by 1/10, to obtain an estimate for the inside zeros, and then added the same estimate for the trailing zeros to obtain a total estimate. $\endgroup$ Sep 8, 2013 at 4:36
  • $\begingroup$ As can be seen elsewhere, the number of trailing zeros has an exact closed form solution. My numerical error analysis for the above estimates showed periodic behavior for the trailing zeros, and chaotic behavior for the inside zeros. With respect to the inside zeros, I suspect they are out of reach, similar in complexity to the distribution of prime numbers. $\endgroup$ Sep 8, 2013 at 4:54
  • $\begingroup$ What is $\Pi$? Also, since the internal zeros overwhelm the trailing zeros, while their 1/10 frequency is only a rough approximation, is this complicated expression really more accurate than the simple $\frac1{10}n\log_{10}n$? $\endgroup$ Dec 12, 2023 at 7:12
3
$\begingroup$

It is unlikely. There are ways to compute the nth digit of certain numbers in certain bases (for example, pi in base 16) without having to compute the entire number, but in most situations, the number or formula for it either has very special properties (e.g. 101*10^n) in order to answer the question, or the work done to answer the question is tantamount to calculating the number, writing it down, and counting the digits. Not only do I know of no way to answer the question otherwise, I will wager a small amount of money that no such nice way will posted here for the next 2 years.

Gerhard "Willing To Formalize The Bet" Paseman, 2012.07.12

$\endgroup$
3
  • 2
    $\begingroup$ Well, that's not completely true. You would save a couple of minutes simply by eliminating 2^24*5^24 from the multiplication. $\endgroup$
    – Gorka
    Jul 13, 2012 at 3:08
  • $\begingroup$ The time saved is dependent and the speed of t and capacity of the multiplier. I agree that it has potential for simplifying the computation. One could also multiply prime powers together. It still smells to me like computing most if not all of the factorial first. Gerhard "Will Lower Yhe Wager Though" Paseman, 2012.07.13 $\endgroup$ Jul 13, 2012 at 17:25
  • $\begingroup$ I think you can say some things about the distribution of digits of some large products of small factors. Keep track of the distribution of subsequences of digits of a length larger than the largest factor. This distribution for $n$ almost determines the distribution for $n*a_i$ for $a_i$ small. However, you lose some control as you have more terms, and for $n!$ it looks like keeping track of the distribution of subsequences is as hard as multiplying the whole number out. $\endgroup$ Jul 13, 2012 at 18:18
2
$\begingroup$

EDIT: this doesn't really work. I'm still a good human being.

Evenly enough, it seems possible to get the number of zeros in the binary expansion of $n!$

One can get a fairly accurate expression for $$\log_2 \; n! = \frac{\log \; n!}{\log 2}$$ from using extra terms in Stirling's formula. Taking the floor of that and adding 1 gives the total number of digits in base two..

Legendre's formula $$ v_2(n!) = \left\lfloor \frac{n}{2} \right\rfloor + \left\lfloor \frac{n}{4} \right\rfloor + \cdots $$ has a companion,

$$ v_p(n!) = \frac{n - S_p(n)}{p-1} $$ where $S_p(n)$ is the sum of the digits when $n$ is written in base $p.$ As all the digits in a base two expansion are $1,$ we find that $S_2(n)$ is simply the count of 1's in the base two expansion of $n.$

Alright, some people, who shall remain nameless, have attempted to cast aspersions on the reputation of your humble servant, pointing out that the number of ones in the binary expansion of $n!$ is not the same as the number of ones in the binary expansion of $n$ itself. I try so hard. Don't change the light bulb, I'll just sit here in the dark.

$\endgroup$
3
  • 1
    $\begingroup$ That would be nice if it were the count of $1$'s in the base two expansion of $n!$. $\endgroup$ Jul 13, 2012 at 3:51
  • 4
    $\begingroup$ Well, crap. ${}{}{}{}{}$ $\endgroup$
    – Will Jagy
    Jul 13, 2012 at 3:57
  • $\begingroup$ Maybe we can do something with $v_p(n!!)$ $\endgroup$ Jul 13, 2012 at 7:21
0
$\begingroup$

We can find a general approximation as follows. First count the number of trailing zeros in $n!$. Since there are more factors of $2$ than factors of $5$ in $n!$, this means that there are: $$ \sum^\infty_{i=1}\left\lfloor{n\over5^i}\right\rfloor $$ zeros in the end of the number. Now, there are $\mathrm{log}(n!)$ digits in $n!$. In the remaining digits (those which are not trailing zeros), each digit has $1/10$th of a chance of being a $0$ (there are numbers for which zeros inside the number appear with frequency; Faber calls these numbers zero-perfect in his answer), so we see that the number of zeros in $n!$ is approximated by: $$ \sum^\infty_{i=1}\left\lfloor{n\over5^i}\right\rfloor-\frac{1}{10}\left(\mathrm{log}(n!)-\sum^\infty_{i=1}\left\lfloor{n\over5^i}\right\rfloor\right) $$ Using Stirling's approximation, this gives about: $$\frac{9}{10}\sum_{i=1}^{\infty}\left\lfloor{\frac{n}{5^{i}}}\right\rfloor+\frac{1}{10}n\log_{10}n-\frac{n}{10\ln 10}+O(\ln n)$$ zeros in $n!$.

I don't think there's an closed form for this, but this gives a good approximation. For example, when $n=32000$ the above formula is only off by $1$. When $n=100$, the above formula gives $37.25$ as it's approximation. It's off by $7.25$.

$\endgroup$
1
  • $\begingroup$ Isn't this what's already done in Halfdan Faber's answer? $\endgroup$ Dec 12, 2023 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.