二項係数の偶奇

パスカルの三角形の奇数部分を塗り潰すとシェルピンスキーのギャスケットが登場することは良く知られている。そこで二項係数が奇数か偶数か判定する方法について考えたことがある。

もちろん、定義通り二項係数を求めようとすると、C言語の int では 13の階乗で int の範囲を超えてしまうので、が大きい場合の二項係数の偶奇を求めるのは難しい。

二項係数の再帰的定義を利用すると、大きな二項係数についても偶奇を求めることが可能であるが、時間がかかりすぎる。例えばを計算するのに423万8千回程度の再帰的計算を行なっている。

これらの問題をどう解決するか、ということで色々考えて、非常にエレガントな方法を考えついたのだが、

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

にほぼ同じ方法が載っていた。