### 42nd Putnam 1981

Problem A1

Let the largest power of 5 dividing 112233 ... nn be 5f(n). What is limn→∞ f(n)/n2 ?

Solution

Answer: 1/8.

Let 5k be the largest power of 5 not exceeding n.

We proceed by looking first at the contribution of the single power of 5 in all multiples of 5, then at the additional contribution from the second power of 5 in all multiples of 25 and so on. A single power of 5 in m appears m times in mm, so the first power of 5 in 5, 10, 15, 20, ... contributes to f(n): 5 + 10 + 20 + ... + 5[n/5] = 5( 1 + 2 + ... + [n/5] ) = 1/2 5 ( [n/5]2 + [n/5] ). Similarly, the second power of 5 in 25, 50, 75, ... contributes an additional 1/2 52 ( [n/52]2 + [n/52] ). And so on. Hence

2 f(n) = 5 ( [n/5]2 + [n/5] ) + 52 ( [n/52]2 + [n/52] ) + ... + 5k( [n/5k]2 + [n/5k]).

Let [n/5i] = n/5i + δi. Then 5i ( [n/5i]2 + [n/5i] ) = 5i ( (n/5i - δi)2 + (n/5i - δi) = n2/5i - 2n δi + 5iδi2 + n - 5iδi.

Hence 2 f(n) = n2∑1/5i - 2n ∑ δi + ∑ 5ii2 - δi) + nk.

Now k = [log5n], so k/n → 0 as n → ∞. Also |δi| and |δi2 - δi| < 1. Hence lim 1/n2 |- 2n ∑ δi + ∑ 5ii2 - δi) + nk| <= lim 2k/n + lim k/n + lim 1/n2 ∑ 5i = 0 + 0 + lim 1/n2 (1/4 (5k+1 + 1) = 0 (since the last term is less than 5/4n).

Hence lim f(n)/n2 = 1/2 (1/5 + 1/52 + ... ) = 1/2 1/5 1/(1 - 1/5) = 1/8.

© John Scholes
jscholes@kalva.demon.co.uk
3 Nov 1999