第2题

若正整数可写成

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

的形式（其中

a_1,a_2,\ldots,a_{100}

是不必互异的非负整数），则称其为「fancy」数。求最小的正整数

n

，使得

n

的任何倍数都不是 fancy 数。

第 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$ 。