Floor exercises

The previous post explained why the number of trailing zeros in n! is

and that the sum is not really infinite because all the terms with index i larger than log₅ n are zero. Here x is the floor of x, the largest integer no greater than x.

The post gave the example of n = 8675309 and computed that the number of trailing zeros is 2168823 using the Python code

 sum(floor(8675309/5**i) for i in range(1, 10))

Now suppose you wanted to calculate this by hand. You would want to be more clever than the code above. Instead of dividing n by 5, and then by 25, and then by 125 etc. you'd save time by first computing

8675309/5 = 1735061,

then computing

1735061/5 = 347012,

and so forth.

Is this calculation justified? We implicitly assumed that, for example,

n/25 = n/5 /5.

This seems reasonable, so reasonable that we might not think to check it, but calculations with floor and ceiling functions can be tricky.

There's a theorem from Concrete Mathematics that can help us.

Let f(x) be any continuous, monotonically increasing function with the property that whenever f(x) is an integer, x is an integer. Then

f(x) = f(x)

and

f(x) = f(x) .

Note that the requirements on f compose. That is, if a function f satisfies the hypothesis of the theorem, so do the compositions ff and fff etc. This means we can apply the theorem above iteratively to conclude

f(f(x)) = f (f(x))

and

f( f(x)) = f (f(x))

and similarly for higher compositions.

The hand calculation above is justified by applying the iterated theorem to the function f(x) = x/5.

Related posts

• Floor, ceiling, bracket
• Complex floor

The post Floor exercises first appeared on John D. Cook.