42nd Putnam 1981

Let the largest power of 5 dividing 1¹2²3³ ... nⁿ be 5^f(n). What is lim_n→∞ f(n)/n² ?

Solution

Answer: 1/8.

Let 5^k 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 m^m, 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]² + [n/5] ). Similarly, the second power of 5 in 25, 50, 75, ... contributes an additional 1/2 5² ( [n/5²]² + [n/5²] ). And so on. Hence

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

Let [n/5ⁱ] = n/5ⁱ + δ_i. Then 5ⁱ ( [n/5ⁱ]² + [n/5ⁱ] ) = 5ⁱ ( (n/5ⁱ - δ_i)² + (n/5ⁱ - δ_i) = n²/5ⁱ - 2n δ_i + 5ⁱδ_i² + n - 5ⁱδ_i.

Hence 2 f(n) = n²∑1/5ⁱ - 2n ∑ δ_i + ∑ 5ⁱ(δ_i² - δ_i) + nk.

Now k = [log₅n], so k/n → 0 as n → ∞. Also |δ_i| and |δ_i² - δ_i| < 1. Hence lim 1/n² |- 2n ∑ δ_i + ∑ 5ⁱ(δ_i² - δ_i) + nk| <= lim 2k/n + lim k/n + lim 1/n² ∑ 5ⁱ = 0 + 0 + lim 1/n² (1/4 (5^k+1 + 1) = 0 (since the last term is less than 5/4n).

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

42nd Putnam 1981

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