階乗を求めるための下限

ネタ元
http://www.kmonos.net/wlog/113.html#_2256100904

階乗を求めるのに、

k! = lim_{n → ∞} n^k / _nC_k

という方法がある。これはどこかで見たことがあるような気がする。ただ、n = (k + 1)^{k + 2}とすれば必ず整数の割り算で正しい答えは出る、というのは見たことがなかった。
この証明は簡単で、

n^k / _nC_k = k! / 1...(1 - (k - 1) / n)

ここに n = (k + 1)^{k + 2} を代入すると、

k! / 1...(1 - (k - 1) / (k + 1)^{k + 2}) < k! / 1...(1 - 1 / (k + 1)^{k + 1}) < k! / (1 - 1 / (k + 1)^{k + 1})^k < k! / (1 - k / (k + 1)^{k + 1}) < k! / (1 - 1 / (k + 1)^k) < k! / (1 - 1 / k!)

だから、正しい答えになります（見にくいですね）。
ただ、この評価はかなーり雑ですよね。もっと小さな n でもだいじょうぶそうですよね。元記事の趣旨とはかけ離れますが、nをどう取るのがよいかをここでは探りたいと思います。
まずは、n の下限をプログラムで求めることを考えましょう。2分探索します。

def C(n, k):
    return 1 if k == 0 else C(n, k - 1) * (n - k + 1) / k

def factorial(k):
    return 1 if k == 0 else k * factorial(k - 1)

def factorial2(k, n):
    return n ** k / C(n, k)

def lower_n(k):
    f = factorial(k)
    
    def lower_n_(min_n, max_n):
        if min_n == max_n:
            return min_n
        
        n = min_n * 2 if max_n == -1 else (min_n + max_n) / 2
        if n == min_n:
            return max_n
        
        f2 = factorial2(k, n)
        if f2 == f:
            return lower_n_(min_n, n)
        else:
            return lower_n_(n, max_n)
    
    return lower_n_(k, -1)

N = 10
for k in range(1, N + 1):
    rough_n = (k + 1) ** (k + 2)
    exact_n = lower_n(k)
    print k, rough_n, exact_n

この結果は、

1 8 2
2 81 4
3 1024 21
4 15625 149
5 279936 1207
6 5764801 10810
7 134217728 105853
8 3486784401 1128977
9 100000000000 13063701
10 3138428376721 163296026

右側が n の下限です。
さて、問題は n をどう評価するかです。ちょっと考えてみたんですが、意外と難しいです。ラフに計算してみたら、k! k² となりました。

1 2 1
2 4 8
3 21 54
4 149 384
5 1207 3000
6 10810 25920
7 105853 246960
8 1128977 2580480
9 13063701 29393280
10 163296026 362880000

右側がそのラフなnです。
また今度、ちゃんと考えてみます。