階乗に含まれる素数の個数

Copyright (C) virtual_high_school, 2022

§1. はじめに

本稿で扱う問題は「$n !$ に含まれる素数 $p$ の個数を求めよ」というものである。
これについては、別のページで取り扱った。（→ 「【知恵袋から】整数」参照。）

本稿ではそこで述べたものとは異なる別解を紹介したい。
その前に、別稿で述べたふつうのやり方を§2 で復習した後、§3 で別解を述べる。

§2. ふつうのやり方

「$100 !$ に含まれる素数 $3$ の個数を求めよ」をふつうのやり方で解いてみよう。

$1$ 〜 $100$ の整数のうち、$3$ の倍数、$3,6,9,\cdots, 99$ には素数 $3$ が含まれる。その個数は

$[\frac{100}{3}]=[33.3\cdots]=33$(個)

である。ここに $[x]$ は実数 $x\geq 0$ に対しては小数点以下を切り捨てた値を表す。($[\mbox{　}]$をガウスの記号と言う。)
ところが、$9$ の倍数には $3$ が $2$個(以上)含まれる。$33$ 個というのはこのうちの $1$ 個分しかカウントされていない。そこで数え落とした $9$ の倍数の個数分だけカウントを増やしておこう。

$[\frac{100}{3}]+[\frac{100}{9}]=33+11=44$(個)

でも、まだ数え落としがある。$27$ の倍数には $3$ が $3$個(以上)含まれるのにこのうちの $2$ 個しかカウントしてなかったので、$3$ 個目も算入して

$[\frac{100}{3}]+[\frac{100}{9}]+[\frac{100}{27}]=33+11+3=47$(個)

もう、お分かりだろう。これを繰り返せばよいのだから、求めるべき個数を $m$ とすれば

$m=[\frac{100}{3}]+[\frac{100}{9}]+[\frac{100}{27}]+[\frac{100}{81}]+[\frac{100}{243}]+\cdots=33+11+3+1+0+\cdots=48$(個)

一見無限和だが、実際には $1$ 〜 $100$ の中に $243$ の倍数はないから、$[\frac{100}{243}]$ 以降の項はすべて $0$ で実質有限和である。

これを一般化すれば、$n !$ に含まれる素数 $p$ の個数 $m$ は

$m=[\frac{n}{p}]+[\frac{n}{p^2}]+[\frac{n}{p^3}]+\cdots$

である。(ルジャンドルの定理)

§3. 別解

前節の問題の別解を次に記す。

$n=100$ を $p=3$進法で表すと

$n=3^4+2\times 3^2+1=10201_{(3)}$

となる。いま $a_{4}=1,a_{3}=0,a_{2}=2,a_{1}=0,a_{0}=1$ とおいて

$n=a_{4}3^4+a_{3}3^3+a_{2}3^2+a_{1}3+a_{0}$

とする。

さて、$3$進法で

$00000,00001,00002,00010,\cdots.10201$

の $100$ 個の整数の中にある、 ($3$ の倍数の個数)＋($9$ の倍数の個数)＋($27$ の倍数の個数)＋$\cdots$ を計算すればよいのだ。

$3$進法の整数 $x_{4}3^4+x_{3}3^3+x_{2}3^2+x_{1}3+x_{0}$ が (ア) $3$ の倍数である条件は $x_{0}=0$ であり、 (イ) $9=3^2$ の倍数である条件は $x_{1}=x_{0}=0$ であり、等々である。

したがって

(ア) $3$ の倍数は $10120$ のような下1桁が $0$ の整数、
(イ) $9$ の倍数は $10100$ のような下2桁が $00$ の整数、
(ウ) $27$ の倍数は $01000$ のような下3桁が $000$ の整数、
(エ) $81$ の倍数は $10000$ のような下4桁が $0000$ の整数

である。次にその個数を求めよう。

(ア) 下1桁が $0$ の整数は
$00010,00020,\cdots,10200$
である。見づらいから下1桁を削除すれば、
$0001,0002,\cdots,1020$, すなわち
$1$ から $a_{4}3^{3}+a_{3}3^2+a_{2}3+a_{1}$ までの整数すべてである。
したがってその個数は $a_{4}3^{3}+a_{3}3^2+a_{2}3+a_{1}$(個)

(イ) 下2桁が $00$ の整数は見づらいから下2桁を削除すれば、
$001,002,\cdots,102$, すなわち
$1$ から $a_{4}3^{2}+a_{3}3+a_{2}$ までの $a_{4}3^{2}+a_{3}3+a_{2}$(個)

(ウ) 下3桁が $000$ の整数は下3桁を削除すれば、
$01,02,\cdots,10$, すなわち
$1$ から $a_{4}3+a_{3}$ までの $a_{4}3+a_{3}$(個)

(エ) 下4桁が $0000$ の整数は下4桁を削除すれば、
$1$ のみ, すなわち $a_{4}=1$(個)

結局(ア)〜(エ)の総計を求めればよい。それは

$a_{4}3^{3}+a_{3}3^2+a_{2}3+a_{1}$
$a_{4}3^{2}+a_{3}3+a_{2}$
$a_{4}3+a_{3}$
$a_{4}$

の総和だが、タテに足して

$a_{4}(1+3+3^2+3^3)+a_{3}(1+3+3^2)+a_{2}(1+3)+a_{1}1$
$=a_{4}\frac{3^4-1}{3-1}+a_{3}\frac{3^3-1}{3-1}+a_{2}\frac{3^2-1}{3-1}+a_{1}\frac{3-1}{3-1}$
$=a_{4}\frac{3^4-1}{3-1}+a_{3}\frac{3^3-1}{3-1}+a_{2}\frac{3^2-1}{3-1}+a_{1}\frac{3^1-1}{3-1}+a_{0}\frac{3^0-1}{3-1}$
$=\frac{1}{3-1} \{ a_{4}(3^4-1)+a_{3}(3^3-1)+a_{2}(3^2-1)+a_{1}(3^1-1)+a_{0}(3^0-1) \}$
$=\frac{1}{3-1} \{ (a_{4}3^4+a_{3}3^3+a_{2}3^2+a_{1}3+a_{0})-( a_{4}+a_{3}+a_{2}+a_{1}+a_{0})\}$
$=\frac{n-(a_{4}+a_{3}+a_{2}+a_{1}+a_{0})}{3-1}$
$=\frac{100-(1+0+2+0+1)}{3-1}=48$

たしかに前節の答に一致する。

一般化しておく。$n=a_{h}p^h+\cdots+a_{1}p+a_{0}$ のとき $n!$ に含まれる素因数 $p$ の個数 $m$ は

$m=\frac{n-(a_{h}+\cdots+a_{1}+a_{0})}{p-1}$