２で何回割り切れるか数えるとき

「20！を2進法で表すと末尾には0が連続して並ぶか」という問題について

解答において、20！は２で何回割り切れるか求める際に、2＾1、2＾2、2＾3、2＾4のそれぞれの倍数を求めて合計しているのですが、なぜこのような計算になるのでしょうか。

No.3 ベストアンサー 回答者： Tacosan 回答日時： 2020/10/27 02:25

まず, ある数を 2進法で表したときに末尾に 0 がどれだけ続くかは, その数が 2 で何回割り切れるかで決まる. んで, 複数の因数の積が 2 で何回割り切れるかは, 個々の因数が何回割り切れるかを考えてその総和をとればいい.

ということを前提に, (20! の因数である) 1～20 の整数を縦に並べ, その横に「それらが何回 2 で割り切れるか」を○の個数で表してみる. すると (最初だけ書くと)
1:
2: ○
3:
4: ○○
5:
6: ○
(以下略) となる. この「○の個数」を「縦に」数えてみればいい.

なお, もともとの「20！を2進法で表すと末尾には0が連続して並ぶか」については (20! は明らかに 4 の倍数だから)
YES
が答えだ.

この回答へのお礼

詳細な回答をありがとうございました。

お礼日時：2020/10/27 10:01

No.2 回答者： metabolian 回答日時： 2020/10/26 20:19

「2で何回も割るより、手間が省けるから」

だと思います。
例えば、2^4=16の倍数だと分かれば、
「20！は2で4回割りきれる」と分かりますから。

この回答へのお礼

回答ありがとうございました。

お礼日時：2020/10/27 10:01

No.1 回答者： kairou 回答日時： 2020/10/26 20:19

10進数の 2 (2¹) を 2進数で表すと 10 で 0 は 1個ですね。

10進数の 4 (2²) を 2進数で表すと 100 で 0 は 2個ですね。
10進数の 8 (2³) を 2進数で表すと 1000 で 0 は 3個ですね。
10進数の 16 (2⁴) を 2進数で表すと 1000 で 0 は 4個ですね。
・・・　　　・・・
これで、見当が付きますか。

この回答へのお礼

回答ありがとうございました。

お礼日時：2020/10/27 10:01