[ 数学 ] n! に含まれる素因数 p の数を求めなさい（ルジャンドルの定理）
[サイトマップを見る ]
ルジャンドルの定理
n! に含まれる素因数 p の数は次のルジャンドルの定理で求めることができます。
$$
\sum_{n=1}^\infty \lfloor \frac{n}{p^i} \rfloor = \lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \lfloor \frac{n}{p^3} \rfloor \cdots
$$
準備
床関数 小数点以下を切り捨てる関数のことです。例えば、$${\lfloor 3.14 \rfloor = 3}$$となります。
説明
例えば，4! に含まれる素因数 2 の数を求めてみましょう。4! は $${4 \times 3 \times 2 \times 1 = 2^3 \times 3 \times 1}$$ ですから，2 は3個あるはずです。ルジャンドルの定理で計算してみましょう。
$$
\lfloor \frac{4}{2} \rfloor + \lfloor \frac{4}{2^2} \rfloor + \lfloor \frac{4}{2^3} \rfloor \\
\lfloor 2 \rfloor + \lfloor 1 \rfloor + \lfloor .5 \rfloor \\
2 + 1 + 0 = 3
$$
$${ \lfloor \rfloor}$$ は床関数です。床関数は，小数点以下を切る関数です。0.5 は 0 になります。
計算結果は 3 です。たしかに正しく計算できていますね。
なぜこれで計算できるのか
この式でなぜきちんと計算できるのか考えてみましょう。
具体的に考えたほうがわかりやすいので，10! の場合，2 がいくつあるかを考えてみましょう。
$$
10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1
$$
上のとおり，10! は、1から10までの整数をすべて掛け合わせた数です。この中に含まれる素数2の個数を求めるには、どうすればいいでしょうか。
まず、10個の数を2で割れる数と割れない数に分けてみましょう。2で割れる数は、2, 4, 6, 8, 10の5つです。つまり、$${\lfloor \frac{10}{2} \rfloor}$$ で求めることができます。
しかし、4や8のように、2で2回割れる数も含まれています。このような数は、2つの2を含んでいるので、先ほどの計算では1つ数えすぎていることになります。
そこで、4で割れる数（2×2で割れる数）の個数を引いてあげます。4で割れる数は4と8の2つなので、$${\lfloor \frac{10}{4} \rfloor}$$ で求めることができます。 同様に、8のように、2で3回割れる数も考えなければなりません。8で割れる数は8の1つだけなので、$${\lfloor \frac{10}{8} \rfloor}$$ で求めることができます。 このように、2で割れる数、4で割れる数、8で割れる数...と、2の累乗で割れる数をすべて数え上げて足し合わせると、10!に含まれる2の個数を正確に求めることができます。
まとめ
ルジャンドルの定理は、一見複雑に見えますが、一つ一つの項が何を表しているのかを丁寧に考えると、理解できるはずです。この式を使うと、n!に含まれる任意の素数の個数を簡単に求めることができます。
[ サイトマップを見る ]
この記事が気に入ったらサポートをしてみませんか？