10\,!\ に含まれる素因数2の個数を求めよ.$階乗の素因数の個数 \\
以下のように,\ $素因数の個数を●で縦に並べて,\ 横に数えるのがポイントである.$ \\
題意の確認のため,\ まずは愚直な方法を示す.\ 以下のようにして,\ 素因数2を8個含むとわかる.
10!\,程度ならばこれで求められてしまうので,\ 実際の試験で問われるのは100!\,などである.
非常に単純かつ本質的な方法が}知られているので,\ 習得してほしい.
自然数を横に並べた表を作り,\ その下に素因数2の個数を●で縦に並べて書く.}
2は●1個,\ 4は2^2\,で2を2個もつから●を縦に2個書くといった具合である.
●は横に見ると規則的に並んでいるから,\ 個数を計算で求めることができる.}
第1段目の●の個数は,\ 2の倍数の個数に等しくなる}から,\ 10÷2=5個である.
第2段目の●の個数は,\ 2^2=4の倍数の個数に等しくなる}から,\ 10÷4=2.5より,\ 2個である.
第3段目の●の個数は,\ 2^3=8の倍数の個数に等しくなる}から,\ 10÷8=1.25\ より,\ 1個である.
2^4=16より,\ 10!\,であれば●が4段以上になることはない.
試験では表を書く必要はない.\ 表をイメージしつつ,\ 2,\ 2^2,\ 2^3\,の倍数の個数を求めて足せば済む.
階乗の素因数の個数問題は,\ 様々な表現で出題される.\ 例えば,\ 以下も本問と全く同じ問題である.
「\,2^n\,が10\,!\ を割り切るときのnの最大値を求めよ」「10\,!\ は2で何回割れるか」} の末尾に連続して並ぶ0の個数を求めよ.の末尾に0が何個連続して並ぶか}」}$
$→ 「\,n!\,に10が何個含まれるか」}$
$→ 「\,n!\,に5が何個含まれるか}」}$ (2は確実に5より多い)
n!\,の末尾の0の個数は,\ n!\,がもつ10の個数に等しい.}
例えば,\ 10を3個もつ5･10^3=5000は,\ 末尾に0が3個並んでいる.
さて,\ 10=2･5より,\ 10を1個もつことは2と5を1個ずつもつということである.
ここで,\ n!\,に含まれる素因数2の個数は素因数5の個数より多い.}
n以下の自然数には,\ 必ず2の倍数のほうが5の倍数よりも多く含まれるからである.
よって,\ 少ないほうの素因数5の個数さえ求めれば,\ 10の個数が求まったことになる}わけである.
ここまで言い換えると,\ 後は前問と同じである.\ 5^4=625より,\ 5^3\,の倍数の個数まで求めれば済む.
ルジャンドルの公式
階乗の素因数の個数については,\ ガウス記号を用いた一般化公式が知られている.
$n以下の自然数に含まれるpの倍数の個数はに含まれる素因数pの個数は$
ガウス記号\gauss x}は,\ xを超えない最大の整数}を表す.
ガウス記号を使うと,\ 例えば100以下の自然数に含まれる3の倍数の個数は\gauss{100}{3と表せる.
実際,\ \gauss{100}{3=\gauss{33.33･･･}=33\,(個)\ である.
ガウス記号を用いて以下を表したのがルジャンドルの公式である.
(n以下のpの倍数の個数)+(n以下のp^2\,の倍数の個数)+(n以下のp^3\,の倍数の個数)+･･････
無限和に思えるが,\ p^k>nのとき0<n}{p^k}<1より\gauss{n}{p^k=0となるから,\ 結局有限和になる.
2^5=32として求めることもできるが,\ 2^5\,のまま計算するのが本質的である.
2^5\,までの2,\ 2,^2,\ 2^3,\ 2^4,\ 2^5\,の倍数の個数をそれぞれ求めればよく,\ すぐに規則性にも気付くだろう.
等比数列の和}になるので,\ 数列(数 B)を学習済みならば公式で素早く求めることができる.
初項a,\ 公比r,\ 項数nの等比数列の和 a(r^n-1)}{r-1}
2^4+2^3+2^2+2^1+1=1+2^1+2^2+2^3+2^4=1(2^5-1)}{2-1}=31
また,\ 規則性があるならば一般化できるはずであり,\ それが過去に京都大などで出題されている.
pを素数,\ nを正の整数とするとき,\ (p^n)\,!\,はpで何回割り切れるか. [\,京都大\,] 50!$を3進法で表したとき,\ 末尾に連続して並ぶ0の個数を求めよ.
$50までに,\ 3の倍数は16個},\ 3^2=9の倍数は5個},\ 3^3=27の倍数は1個}ある.$
∴ 16+5+1=22\ (個)}
n進法は後に学習する内容だが,\ 関連問題としてここで取り上げる.
10進数と3進数は,\ {3^1}_{(10)}=10_{(3)},\ {3^2}_{(10)}=100_{(3)},\ {3^3}_{(10)}=1000_{(3)},\ ･･････\ のように対応する.
結局,\ 50!_{(10)}\,が素因数3を何個もつか}を求めることに帰着する.
