Floor exercises

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

\sum_{i=1}^\infty \left\lfloor \frac{n}{5^i} \right\rfloor

and that the sum is not really infinite because all the terms with index i larger than log5 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

Leave a Reply

Your email address will not be published.