52! の桁数を電卓なしで見積もる方法
How Big Are Factorials?
Eli Bendersky が、52! の桁数を暗算で推定する方法を紹介。Gamma 関数と Stirling の近似を出発点に、Laplace の方法で導出し、実用的な式を提示する。52! の実際の桁数 68 に対し、推定値もほぼ一致する。巨大な数の桁数をざっくり掴むための数学的背景を解説した記事。
実際の答えは 68 なので、これは非常に近い！
- Sharlin
n! の桁数をざっくり見積もる手っ取り早い近似は n lg n で、これは不等式
1 * 2 * … * n ≤ n * … * n
によって n! を上から近似します。
(この近似はアルゴリズムの授業で多くの人が見覚えがあるはずです。)
より厳密な上限が欲しければ n lg n - n/2 を使うか、あるいは 1/2 の代わりに ln 10 のより良い近似を使うといいでしょう。これはスターリングの近似から来ていて、
ln n! = n ln n - n + O(ln n)
であることに注意します。
- ninju
著者が記事の冒頭で 52! にさりげなく言及したことで、何年も前に見た古いウェブページを思い出しました
https://czep.net/weblog/52cards.html
このページの年齢を特定する方法を知っている人はいますか？(少なくとも20年前のものに違いありません)
- movpasd
スターリングの近似は統計力学でもよく使われます。というのも、状態空間のサイズの対数を計算することがよくあり、それはつまり組み合わせ論がたくさん、したがって階乗がたくさんということを意味するからです。さらに連続的なので微積分ができます。