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