高校の数学Aの教科書に、ある自然数Nが２の倍数かどうかを判定する方法が説明されていて、
Nの一の位の数(0~9)をaとすると、適切にkを選べば、
N=10k + a
と表現できて10kは必ず2の倍数なので、一の位の数のaが２の倍数かどうかだけ見ればNが２の倍数かどうかを判定できるというものが説明されています。
で、ある自然数Nが4の倍数かどうかを判定するときは、おなじような方法で、
N=100k + a
として、下2桁aが４の倍数かを調べればよいとされています。
で、練習問題に８の倍数を判定する方法を答えよとなっているわけです。
教科書にこういう感じで問題がでてくるときは、直前の方法を使ってその延長線上で解けることがおおいです。
で、結論からいうと１０００は８の倍数なので、８の場合は下３桁を調べればよいわけです。
で、ちょっとおもしろいなと思ってその仕組みみたいなのを考えてみました。
８＝２×２×２
これが、10とか100とか1000とかの約数ならおいしいわけですね。
で、２というのは５を掛けると１０になってくれるので、
8×５×５×５=(２×5)×(２×5)×(２×5)=10×10×10=1000
この感じで、2^n は10^nの約数なので、ある自然数Nが2^nの倍数かどうかの判断は、下n桁だけ見ればよいとなります。
数学に詳しい方ならわらっちゃうほど簡単なことなんでしょうけど、私はこれを”発見”してすこしうれしかったです。
プログラミングでアルゴリズムに落とし込むとしたら、もっと効率的なのがあるのだなとちょっとウェブをサーチして思いました。
