OMCB004(F) - Legendre の定理の近似

　Legendre の定理の近似について紹介しておきます．
　今回の問いであれば，この近似でも十分に耐えうる粗さです（理由は後述します）．

　まず，Legendre の定理とは次のようなものでした．
　　定理：自然数 $n$ と素数 $p$ に対して，$n!$ を $p$ で割り切れる最大の回数は $\sum\limits _{k=1}^{\infty} \left\lfloor \dfrac{n}{p^k} \right\rfloor$ である．
　ここで，床関数を外す近似を考えると，次の式を得ます． 　$$\sum\limits _{k=1}^{\infty} \left\lfloor \dfrac{n}{p^k} \right\rfloor \fallingdotseq \sum\limits _{k=1}^{\infty} \dfrac{n}{p^k} = \dfrac{n}{p-1}$$ 　実際にこの近似を用いてみると，$2244!$ については次のように書き表されます． 　$$2244! \fallingdotseq 2^{\frac{2244}{2-1}}×3^{\frac{2244}{3-1}}×5^{\frac{2244}{5-1}}×7^{\frac{2244}{7-1}}× \cdots =2^{2244}×3^{1122}×5^{561}×7^{374} \cdots$$ 　正しい値は $2^{2240}×3^{1120}×5^{557}×7^{371}× \cdots$ なので，そう大きくは外していないことがわかります．

　以下では，この近似の精度について考えていきます．
　$x=\lfloor \log _p n \rfloor$ と置いて，近似値と真の値の差を取ります． $$\begin{aligned} \sum\limits _{k=1}^{\infty} \left(\dfrac{n}{p^k}-\left\lfloor \dfrac{n}{p^k} \right\rfloor \right) &= \sum\limits _{k=1}^{x} \left(\dfrac{n}{p^k}-\left\lfloor \dfrac{n}{p^k} \right\rfloor \right) + \sum\limits _{k=x+1}^{\infty} \left(\dfrac{n}{p^k}-\left\lfloor \dfrac{n}{p^k} \right\rfloor \right)\\ &\lt \sum\limits _{k=1}^{x} 1 + \sum\limits _{k=x+1}^{\infty} \dfrac{n}{p^k}\\ &= x+\dfrac{n}{p^x(p-1)} \end{aligned}$$ 最後の項 $\dfrac{n}{p^x(p-1)}$ については，$p^x \leq n \lt p^{x+1}$ であったことから，おおよそ $1$ になります．
　以上の議論から，ここで紹介した近似は， $n$ を $p$ 進数で表したときの桁数程度の誤差を生じうるとわかります（なお，以上の議論を参考にすれば，この近似は必ず真の値より大きい方にずれることもわかります）．

　振り返って今回の問いですが，$2244$ を $2$ 進数で表すと $12$ 桁になります．
　従って，今回の近似で得た $2^{2244}×3^{1122}×5^{561}×7^{374} \cdots$ ですが，指数を $500$ で割った商であれば，真の値と一致することがわかります．
　もし今回の問いが，$2244!$ でなく $2024!$ だった場合には，この近似を使って良いかは十分注意する必要があります．
　二つの値を調べてみると，
　　近似値：$2^{2024}×3^{1012}×5^{506}×7^{337 \frac{1}{3}}×\cdots$
　　真の値：$2^{2017}×3^{1006}×5^{503}×7^{335}×\cdots$
と，ちょっと怖い感じがします（実際は，$\lfloor \log_2 2024 \rfloor =11$，$\lfloor \log_3 2024 \rfloor =6$，$\lfloor \log_5 2024 \rfloor =4$ なので問題ありません）．

　以上，近似についての紹介でした．