Back to Advanced source practice
AdvancedNumber System -- Digits & Factorials -- Very HardTITA Source: LaTeX
Number System/Digits & Factorials

Question

Let kk be the largest positive integer such that 5k5^{k} divides

1!2!3!50!. 1! \cdot 2! \cdot 3! \cdots 50!.

Find kk.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Answer

262262.}

Detailed solution

Number of 55s dividing n=150n!=n=150v5(n!)\prod_{n=1}^{50} n! = \sum_{n=1}^{50} v_5(n!) where v5(n!)=n/5+n/25+n/125+v_5(n!) = \lfloor n/5 \rfloor + \lfloor n/25 \rfloor + \lfloor n/125 \rfloor + \cdots.

For n50n \le 50, v5(n!)=n/5+n/25v_5(n!) = \lfloor n/5\rfloor + \lfloor n/25\rfloor (higher terms vanish).

n=150n/5\sum_{n=1}^{50} \lfloor n/5 \rfloor: n/5=k\lfloor n/5 \rfloor = k for n{5k,5k+1,5k+2,5k+3,5k+4}n \in \{5k, 5k+1, 5k+2, 5k+3, 5k+4\}, contributing 5k5k.

  • n=14n = 1\text{--}4: 00, sum 00.
  • n=59n = 5\text{--}9: 11, sum 55.
  • n=1014n = 10\text{--}14: 22, sum 1010.
  • n=1519n = 15\text{--}19: 33, sum 1515.
  • n=2024n = 20\text{--}24: 44, sum 2020.
  • n=2529n = 25\text{--}29: 55, sum 2525.
  • n=3034n = 30\text{--}34: 66, sum 3030.
  • n=3539n = 35\text{--}39: 77, sum 3535.
  • n=4044n = 40\text{--}44: 88, sum 4040.
  • n=4549n = 45\text{--}49: 99, sum 4545.
  • n=50n = 50: 1010, sum 1010.

Total: 0+5+10+15+20+25+30+35+40+45+10=2350 + 5 + 10 + 15 + 20 + 25 + 30 + 35 + 40 + 45 + 10 = 235.

n=150n/25\sum_{n=1}^{50} \lfloor n/25 \rfloor: 00 for n24n \le 24, 11 for n[25,49]n \in [25, 49] (2525 values), 22 for n=50n = 50. Sum =25+2=27= 25 + 2 = 27.

Total k=235+27=262k = 235 + 27 = 262.

Verified answer: 262262.

Why this is CAT-level: Double summation nv5(n!)\sum_n v_5(n!) instead of v5(single factorial)v_5(\text{single factorial}); the structural switch is non-obvious and brute-force expansion is infeasible.