右から割り算

自然数 \(n\) と素数 \(p\) が与えられて、\(n\) が \(p\) で割り切れるかどうか判定したいとしよう。 ふつうは余りを求めて、それが \(0\) だったら割り切れる、それ以外なら割り切れない、と判断する。 しかし、暗算でそんな計算をするとき、思い返してみると右から桁を減らしていくことが多い。 たとえば \(211\) が \(13\) で割り切れないことを確かめようとする場合、1の位の \(1\) を打ち消すために \(91=7\times 13\) を引き、残りが \(120\) だから \(13\) では割り切れない、と思考を進めるわけである。

再帰的にこんな手続き \(f(n, p)\) を定義すればいい。

1. \(n=0\) ならば True を返す。
2. \(n\) が \(10\) で割り切れるならば \(f(n/10, p)\) を返す。
3. \(n\) の1の位と同じ1の位を持つ \(p\) の倍数(のうち最小のもの)を \(kp\) とするとき、\(n\ge kp\) ならば \(f(n - kp, p)\) を返し、\(n< kp\) ならば False を返す。

いくつか注意を述べると、まず \(p\) は \(10\) と互いに素の場合にだけ適用できる。 その \(10\) は \(d\)-進数の \(d\) だと思って良い(プログラムで実現するときは \(2\)-進数で考えることだろう)。 \(kp\) は事前にテーブルを用意しておいて辞書引きすれば良い(というか \(p\) の1の位で \(k\) は決まってしまう)。 特に\(2\)-進数ならば\(k\)は常に\(1\)なので話が簡単である。

他の人、あるいは既存のプログラムで、この方法で割り切れるかどうかの判定を行っている例があるのかどうか知りたいところである。