整数論や競技プログラミングを学んでいると、「階乗に含まれる素因数の個数」を調べる場面によく出会います。
その中でも興味深い性質として、
「n!に含まれる素因数2の個数は n − f(n) になる」
という関係があります。
ここで f(n) は、n を2進数で表したときの1の個数、いわゆるビットカウント関数です。
この式は偶然のように見えますが、実は有名な整数論の公式と深くつながっています。
まず「n!に含まれる素因数2の個数」とは
例えば、
6! = 720
を素因数分解すると、
720 = 2⁴ × 3² × 5
です。
つまり、6!には素因数2が4個含まれています。
この「何個含まれるか」を表す記号として、整数論ではよく
v₂(n!)
が使われます。
有名なのはルジャンドルの公式
実は、階乗に含まれる素因数の個数には有名な公式があります。
それがルジャンドルの公式です。
素数pについて、
v_p(n!) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + …
となります。
特に p=2 の場合は、
v₂(n!) = ⌊n/2⌋ + ⌊n/4⌋ + ⌊n/8⌋ + …
です。
これが「n!に含まれる2の個数」を求める基本公式として知られています。
n−f(n) になるのは本当？
はい、これは本当に成り立ちます。
しかも、ルジャンドルの公式から導くことができます。
結論を書くと、
v₂(n!) = n − s₂(n)
となります。
ここで s₂(n) は、nの2進表示における1の個数です。
つまり、質問にある f(n) と同じものです。
13の場合で確認してみる
例えば n=13 のときを考えます。
13 を2進数で表すと、
1101₂
です。
1の個数は3個なので、
f(13)=3
となります。
したがって、
13−f(13)=13−3=10
です。
一方、ルジャンドルの公式で計算すると、
⌊13/2⌋ + ⌊13/4⌋ + ⌊13/8⌋
= 6 + 3 + 1 = 10
となり、確かに一致します。
なぜ2進数の1の個数が関係するのか
ここがこの性質の面白いところです。
nを2進数で表すと、
n = a₀2⁰ + a₁2¹ + a₂2² + …
となります。
ここで各 aᵢ は0か1です。
2進数の各桁の和、つまり
a₀+a₁+a₂+…
がビットカウント関数になります。
一方、ルジャンドルの公式の床関数の和を整理すると、「nから2進数の桁和を引いたもの」になることが知られています。
つまり、
2進数の情報が、そのまま2の指数に反映されている
という非常に美しい関係があるのです。
これは定理として知られている？
はい、この関係自体は整数論ではよく知られています。
特に、
- ルジャンドルの公式
- 2進数の桁和との関係
- p進評価
の話題の中で頻繁に登場します。
単独で特別な名前が付いている場合もありますが、多くは「ルジャンドルの公式の系」や「2進表示による表現」として扱われます。
競技プログラミングや整数論の入門書でも有名な性質です。
一般の素数pでも似た式がある
実は、この話は2だけに限りません。
一般の素数pについても、
v_p(n!) = (n − s_p(n)) / (p−1)
という形になります。
ここで s_p(n) は、nをp進数表示したときの桁和です。
2進数だけでなく、3進数や5進数でも似た構造が現れるのです。
まとめ
「n!に含まれる素因数2の個数は n−f(n)」という性質は、実際に成り立つ有名な結果です。
これはルジャンドルの公式と2進数の桁和の関係から導かれます。
特に、
v₂(n!) = n − f(n)
という式は、整数論では非常に美しい関係として知られています。
階乗・2進数・素因数分解という一見別々の話題が、実は深くつながっている好例と言えるでしょう。
コメント