数学A 整数問題 問題 55 解説

方針・初手

$219!$ が $2^n$ で割り切れるが $2^{n+1}$ で割り切れないということは、$219!$ に含まれる素因数 $2$ の個数が $n$ であるということである。

したがって、$1,2,\ldots,219$ の中に含まれる $2$ の因数の総数を数えればよい。

解法1

$219!$ に含まれる素因数 $2$ の個数は、次のように求められる。

まず、$2$ の倍数はそれぞれ少なくとも $2$ を $1$ 個含むので、

$$ \left\lfloor \frac{219}{2} \right\rfloor = 109 $$

個ある。

次に、$4$ の倍数はさらにもう $1$ 個の $2$ を含むので、

$$ \left\lfloor \frac{219}{4} \right\rfloor = 54 $$

個を加える。

同様にして、$8,16,32,\ldots$ の倍数についても数える。よって、$219!$ に含まれる $2$ の個数は

$$ \left\lfloor \frac{219}{2} \right\rfloor + \left\lfloor \frac{219}{4} \right\rfloor + \left\lfloor \frac{219}{8} \right\rfloor + \left\lfloor \frac{219}{16} \right\rfloor + \left\lfloor \frac{219}{32} \right\rfloor + \left\lfloor \frac{219}{64} \right\rfloor + \left\lfloor \frac{219}{128} \right\rfloor $$

である。

それぞれ計算すると、

$$ \begin{aligned} \left\lfloor \frac{219}{2} \right\rfloor &= 109,\\ \left\lfloor \frac{219}{4} \right\rfloor &= 54,\\ \left\lfloor \frac{219}{8} \right\rfloor &= 27,\\ \left\lfloor \frac{219}{16} \right\rfloor &= 13,\\ \left\lfloor \frac{219}{32} \right\rfloor &= 6,\\ \left\lfloor \frac{219}{64} \right\rfloor &= 3,\\ \left\lfloor \frac{219}{128} \right\rfloor &= 1. \end{aligned} $$

また、$256>219$ なので、これ以上は加える必要がない。

したがって、

$$ n=109+54+27+13+6+3+1=213 $$

である。

解説

階乗に含まれる素因数の個数を求める典型問題である。

$2$ の倍数を数えるだけでは、$4,8,16$ などに含まれる追加の $2$ を取りこぼす。そこで、$2,4,8,16,\ldots$ の倍数の個数を順に足し上げる。

一般に、$m!$ に含まれる素因数 $p$ の個数は

$$ \left\lfloor \frac{m}{p} \right\rfloor + \left\lfloor \frac{m}{p^2} \right\rfloor + \left\lfloor \frac{m}{p^3} \right\rfloor +\cdots $$

で求められる。

答え

$$ \boxed{213} $$