Trailing zeros of factorials, revisited

I needed to know the number of trailing zeros in n! for this post, and I showed there that the number is

Jonathan left a comment in a follow-up post giving a brilliantly simple approximation to the sum above:

... you can do extremely well when calculating the number of trailing 0's by dropping the floor functions and using all the terms of the infinite series, which leaves you with just n/4.

In symbols,

And in case n is not a multiple of 4, we can take the floor of n/4 as our estimate.

For example, let n = 8324228646. Then the exact number of trailing zeros in n! is 2081057156, and n/4 = 2081057161 is only off by 5.

The approximation above is also an upper bound since removing a floor either makes no difference or makes things bigger.

We can make the upper bound a tiny bit tighter by noting that the infinite sum on the left is really a sum up to k = log₅ n and so

The end result never differs from n/4 by more than 1, so it's hardly worth it. However, the calculation above can be modified slightly to get a lower bound.

Since x > x - 1, we have

So the number of trailing zeros in n! is greater than

n(1 - 5^-k)/4 - k

and no more than

n(1 - 5^-k)/4.

Applying this to the example above where n = 8324228646, we have k = 14, and lower bound 2081057147 and upper bound 2081057161, The exact number is 2081057156. Our lower bound was 9 below the exact value, and the upper bound was 5 above the exact value.

The post Trailing zeros of factorials, revisited first appeared on John D. Cook.