100! の末尾に 0 は何個並ぶか？階乗の素因数を数える

$100!$ の末尾には $0$ が 24 個並びます。$15!$ は $2$ でちょうど 11 回まで割り切れる。

どちらも $100!$ や $15!$ を計算していません。素因数が何回現れるかだけを、割り算の積み重ねで数えました。

倍数の個数を重ねて数える

$15!=1\times 2\times 3\times \cdots \times 15$ に、$2$ は何回現れるか。まず $2$ の倍数を数えます。

$2,4,6,8,10,12,14$ の 7 個。ここから $2$ が 1 個ずつ出るので、まず 7 回。

ただし $4$ は $2$ を 2 個持っています。$4$ の倍数からもう 1 回ずつ、$8$ の倍数からさらに 1 回ずつ数える必要がある。

丸の総数が、$15!$ に含まれる $2$ の個数です。$7+3+1=11$ 個。

ルジャンドルの公式

この数え方をそのまま式にしたものが、次の形です^[1]。$\lfloor x\rfloor$ は $x$ を超えない最大の整数を表します。

$$v_p(n!)=\lfloor \frac{n}{p}\rfloor +\lfloor \frac{n}{p^2}\rfloor +\lfloor \frac{n}{p^3}\rfloor +\cdots$$

$p^k$ が $n$ を超えると項は $0$ になるので、和は途中で止まります。無限に足す必要はありません。

第 1 項が $p$ の倍数の個数、第 2 項が $p^2$ の倍数の個数。$p^2$ の倍数は 2 回ぶん数えられ、うまく重なります^[3]。

例：15! に含まれる 2 の個数

$15$ を $2$、$4$、$8$、$16$ で割った商を並べます。

$$\begin{array}{rl}{v}_2(15!)& =\lfloor \frac{15}{2}\rfloor +\lfloor \frac{15}{4}\rfloor +\lfloor \frac{15}{8}\rfloor \\ & =7+3+1=11\end{array}$$

$16$ で割ると商が $0$ なので、そこで打ち切り。$15!$ は $2^{11}$ で割り切れ、$2^{12}$ では割り切れません。

前の商を次々に $2$ で割ってもよい。$15\to 7\to 3\to 1\to 0$ と落として、$7+3+1$ を足すだけです。

例：100! の末尾に並ぶ 0

末尾の $0$ の個数は、$10$ で何回割り切れるかと同じ。$10=2\times 5$ なので、$2$ と $5$ の組がいくつ作れるかを見ます^[4]。

$5$ の個数は $20+4=24$。$2$ の個数は $50+25+12+6+3+1=97$ もあります。

組は少ないほうで決まるので、$0$ は 24 個。$100!$ の末尾には $0$ が 24 個並びます。

5 だけ数えれば足りる理由

$2$ の倍数は $5$ の倍数よりずっと多く現れます。$n$ が大きくなっても、この差は縮まりません。

だから $10$ の個数は、いつでも $5$ の個数のほうで決まる。末尾の $0$ を数えるときは、$5$ だけ見れば足ります^[4]。

例：1000! の末尾に並ぶ 0

$1000$ を $5$ で割り続けます。$200$、$40$、$8$、$1$ と落ちて、次は $0$。

$$200+40+8+1=249$$

249 個です^[2]。$1000!$ は $2568$ 桁あるので、全体のおよそ 1 割が末尾に並ぶ $0$ ということになる。

おおよその見当もつきます。$\frac{n}{5}+\frac{n}{25}+\cdots$ は $\frac{n}{4}$ に近づくので、$n!$ の末尾の $0$ はおよそ $\frac{n}{4}$ 個^[2]。

例：100! に含まれる 7 の個数

$\lfloor \frac{100}{7}\rfloor =14$、$\lfloor \frac{100}{49}\rfloor =2$、$\lfloor \frac{100}{343}\rfloor =0$。

合わせて 16 個。$100!$ は $7^{16}$ で割り切れます。

割る数が大きいほど項の数は減る。$p$ が $n$ の半分を超えれば、項は第 1 項だけになります。

例：末尾の 0 がちょうど 6 個になる n

$v_5(n!)=6$ をみたす $n$ を探します。$\lfloor \frac{n}{5}\rfloor +\lfloor \frac{n}{25}\rfloor =6$ という条件です。

$n=24$ なら $4+0=4$。$n=25$ で $5+1=6$ になり、条件をみたします。

$n=26$ から $29$ までは商が変わらず $6$ のまま。$n=30$ で $6+1=7$ に上がります。

答えは $25,26,27,28,29$ の 5 つ。ここで $5$ が飛ばされている点も見ておきたい。

別の書き方：桁の和を使う

同じ指数は、$n$ を $p$ 進法で書いたときの桁の和からも出ます^[1,2]。桁の和を $s_p(n)$ と書きます。

$$v_p(n!)=\frac{n-s_p(n)}{p-1}$$

$p=2$ なら分母が $1$ なので、$v_2(n!)=n-s_2(n)$ とさらに簡単になります。

例：2 進法で確かめる

$15$ は $2$ 進法で $1111$ です。桁の和は $4$ なので $v_2(15!)=15-4=11$。

割り算で出した $7+3+1=11$ と一致しました。どちらの道でも同じ値に着きます。

$100$ は $2$ 進法で $1100100$、桁の和は $3$。$v_2(100!)=100-3=97$ で、これも先ほどの値と合っています。

$100$ を $5$ 進法で書くと $400$ で桁の和は $4$。$\frac{100-4}{5-1}=24$ となり、末尾の $0$ の個数に戻りました。

検算

小さい階乗なら直接計算して確かめられます。$10!=3628800$ で、末尾の $0$ は 2 個。

公式でも $\lfloor \frac{10}{5}\rfloor =2$ で一致します。$2$ の個数は $5+2+1=8$ で、$3628800=2^8\times 14175$。

商を順に割っていくとき、途中で $0$ にならないうちに打ち切っていないかも見ます。足し忘れが最も多い誤りです。

よくあるミス

割って、商を足して、$0$ になったら止める。手順はこれだけなので、$1000!$ でも数十秒で終わります。

出典