球面倶楽部零八式 mark II

クソブログ

二項係数は2で何回割れるか

数学プログラム

結論から言えば、ビット演算子を用いて

bitCount( n ^ r ^ (n-r) )

となる。ここで bitCount は引数の2進数表示における1の個数である。

「二項係数の偶奇」という記事で説明したことから直ちに2で割れる回数は
$\lfloor \frac{a+b}{2^k} \rfloor=\lfloor \frac{a}{2^k} \rfloor+\lfloor \frac{b}{2^k} \rfloor+1$ が成り立つ場所の個数に一致することがわかる。
つまり、

${}_nC_{r}$ が2で何回割れるかは $r+(n-r)$ を2進数で足し算を行なったときに生ずる繰り上がりの回数に一致する。

例えば、 ${}_{10}C_{3}=120=2^3\times 15$ において、 $3_{(10)}+7_{(10)}=11_{(2)}+111_{(2)}=1010_{(2)}$ の計算で繰り上がりが3ヶ所で生じている。

一般に2つの2進数の計算において、2進数に繰り上がりが生じたとき、その1つ上の位の計算は最大3つの和となるので、二重に繰り上がりは生じない、つまり、 $n$ の2進数での桁数を $k$ とすると、 $r+(n-r)$ の計算の繰り上がりの数は最大 $k-1$ なので、 ${}_nC_{r}$ が $2^k$ で割り切れることはありえないことがわかる。

例えば、 $18_{(10)}=10010_{(2)}$ は5桁の2進数なので、 ${}_{18}C_{r}$ が $32$ で割り切れることはない。 ${}_{18}C_{7}=31824$ は $16$ で割り切れる。商は $1989$ である。繰り上がりの回数を確認すると
$7_{(10)}+11_{(10)}=111_{(2)}+1011_{(2)}=10010_{(2)}$ の計算で繰り上がりが4ヶ所で生じている。

繰り上がりが生じてた場合、1つ上の位に1が足されることから、繰り上がりが生じたときの1つ上の位の計算は
$0+0=1$ 、 $0+1=0$ 、 $1+0=0$ 、 $1+1=1$ のいずれかになることがわかる。つまりそのような場所の数を数えれば良い。

よって、筆算で行なうには、 $n$ 、 $r$ 、 $n-r$ の2進数表示を並べて、1の個数が奇数個になる桁が何箇所あるかを数えれば、それが求める答えとなる。

これを式で書こう。排他的論理和 XOR は交換律と結合律をみたす論理演算であり、1の数が奇数個であれば1、偶数であれば0を返す論理演算である。よって、 $n$ XOR $r$ XOR $(n-r)$ の2進数表示における1の個数が繰り上がりの回数となり、それが求める答えとなる。

2020.10.19追記

ラマヌジャンの遺した関数 (本格数学練習帳第1巻)

ラマヌジャンの遺した関数 (本格数学練習帳第1巻)

作者:D.フックス,S.タバチニコフ
発売日: 2012/07/28
メディア: 単行本（ソフトカバー）

■

を久しぶりに読み返すと、p.44 に、二項係数が素数 $p$ で割り切れる回数は， $p$ 進記法の加法での繰り上がり回数である(クンマー、1852)とある．

これまでの結果からクンマーの定理を導くという楽しい仕事は読者に残しておこう．
（演習問題2.5になっているが、解答はない)．

2021.03.13追記
この Kummer の定理、

2021年(令和3年)東京大学-数学(理科)[4] - [別館]球面倶楽部零八式markIISR

で出題されたこともあって受験業界でも大分有名になりつつある．

受験数学界で確認した初出は，
2015年(平成27年)東京大学前期-数学(理科)[5] - [別館]球面倶楽部零八式markIISR
でも触れたが，

大学への数学2001年2月号に雲幸一郎さんの「素数で何回割り切れるか」という記事に
「p進展開で a+b を計算するときに"繰り上がり"が何回起こるかで決まります。」
と書いてある．

雲ですがなにか？

Kummer の定理の証明は

を参照しても良い。