階乗の連続積÷連続階乗で2の指数を求める方法

今回はパズル的な数学問題として、連続階乗の積を別の連続階乗で割った際に2で何回割り切れるかを考えます。大きな数字ですが、階乗の性質と2の指数の求め方を使えば整理可能です。

問題の整理

与えられた式は以下の通りです。

(10200!・10400!・10600!・・・19600!・19800!・20000!) ÷ (100!・300!・500!・・・9500!・9700!・9900!)

求めたいのは、この分数が2で何回割り切れるか、すなわち2の指数です。

2の指数の求め方

階乗 n! の中の素因数 2 の指数は、以下で求められます。

v_2(n!) = n/2 + n/4 + n/8 + …

これは n を 2, 4, 8,… で割った整数部分を足していく方法です。

分子と分母の指数の差

連続階乗の積の場合、分子と分母の指数をそれぞれ計算して、差を取ります。つまり:

v_2(分数) = Σ v_2(分子の階乗) – Σ v_2(分母の階乗)

ここで分子は 10200!,10400!,…,20000! の偶数ステップで 50 個ほど、分母は 100!,300!,…,9900! の 50 個程度の階乗です。

近似的な整理

直接計算は大変ですが、2の指数は階乗の大きさにほぼ比例します。n! の 2 の指数はおおよそ n-(n の二進数における1の個数) で近似できます。連続階乗の積の場合は、項ごとに指数を足して、分母の指数を引くことで求められます。

より正確に求めるには、プログラムで各階乗の2の指数を計算し、全て足し引きする方法が確実です。

まとめ

この問題は大きな階乗の指数計算ですが、重要なのは「v_2(n!) = n/2 + n/4 + …」という公式を使って、分子と分母の2の指数を別々に計算し、差を取ることです。手作業での計算は現実的ではないため、計算機やプログラムを使うと便利です。途中経過として、分子の階乗を順に足していき、分母の階乗を引くことを意識しましょう。