52! の桁数を電卓なしで見積もる方法
How Big Are Factorials?
Eli Bendersky が、52! の桁数を暗算で推定する方法を紹介。Gamma 関数と Stirling の近似を出発点に、Laplace の方法で導出し、実用的な式を提示する。52! の実際の桁数 68 に対し、推定値もほぼ一致する。巨大な数の桁数をざっくり掴むための数学的背景を解説した記事。
実際の答えは 68 なので、これは非常に近い！
HNでの議論
41- svobodamartin
私のお気に入りは52!秒を使ったやつだ：
52!から0までカウントダウンするタイマーを開始する。
そして、10億年に1歩のペースで地球の赤道を歩いて一周する。
赤道を一周したら（10億年に1歩で）、太平洋から水を一滴すくい出す。
そして、赤道を歩くプロセスを繰り返し、一周するごとに一滴ずつ水を減らし続ける。
海が完全に干上がったら、海を再び満たし、自分の下に紙を一枚置く。
さて、再びこの歩く、水を減らす、紙を置くというプロセスを繰り返す。
紙の山が太陽に届いたら、さらにもう1000回繰り返す。
これだけやっても、タイマーはまだ3分の1ほどしか進んでいない。
- ninju
著者が記事の冒頭で52!にさりげなく触れたことで、何年も前に見た古いウェブページを思い出した
https://czep.net/weblog/52cards.html
このページの年齢を特定する方法を知っている人はいるだろうか（少なくとも20年前のものに違いない）
- andrewla
これはBender & Orszagの分析を思い起こさせる。彼らは積分ではなく差分方程式（形式数学では少し失われた芸術で、非常に19世紀的な雰囲気がある）を通じてこの問題にアプローチしている。
ガンマ関数を導入する代わりに、log(F_n) - log(F_n-1) = log(n)という観察から始め、この差分を積分に類似したものとして扱うと、F_n ~= nlogn + nが主要な漸近的振る舞いであることがわかる。これは代入と代数だけで明らかであり、微積分は必要ない（ただし「事前に答えを知っている」ことは役立つ）。
そこから、この誤差項をF_n = n^n * e^n * E_nとして扱い、同じ関係式（F_n = n * F_n-1）に代入して、その誤差項が漸近的にどのようになるかを導き出し、元の記事の積分が導くのと同じ結論に至る。
- 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)
であることを述べている。
- abetusk
lg(n!)はおおよそ(n lg n)として成長する。もちろん定数は重要だが、それが大まかな見積もりだ。
余談だが、0から(n-1)までの数を配列に入れると、n!通りの配置があるので、各配置を表現したり区別したりするにはn lg nビットが必要になる。つまり、ある意味で、入力状態を区別して順序状態にマッピングできるような写像を取るには、少なくともO(n lg n)時間がかかり、これは基本的なソートアルゴリズムの標準的な実行時間だ。
追加の仮定（nが最大要素より大きい、要素の分布など）があれば、これを減らすのに役立つ。