第2問

2^{a_1}+2^{a_2}+\cdots+2^{a_{100}}

（

a_1,a_2,\ldots,a_{100}

は互いに異なるとは限らない非負整数）の形に表せる正整数を「fancy」と呼ぶ。

n

のどの倍数も fancy な数にならないような最小の正整数

n

を求めよ。

ステップ 2/5: より小さい

k

はどれも fancy な倍数を持つ

前のステップ次のステップ

2^s k=2^{a_1+s}+\cdots+2^{a_r+s},\quad s=100-r;\quad 2^j=2^{j-1}+2^{j-1}\text{ increases the number of powers by one}

詳しい解説

まず $s=100-r$ として $k$ の二進展開に $2^s$ を掛ける。 $s=0$ なら、これはすでにちょうど $100$ 個の二べきの和である。 $s>0$ なら、 $2^j=2^{j-1}+2^{j-1}$ によって、正の指数をもつ項を一つずつ選び、繰り返し分割する。最初に $2^{a_r+s}$ を選べば、これを $s$ 回行えて、値を変えずに項数を $r$ から $r+s=100$ に増やせる。したがって $k$ は fancy な倍数を持ち、fancy な倍数を持たない最小の $n$ は $n\ge2^{101}-1$ を満たす。