第2题

若正整数可写成

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

的形式（其中

a_1,a_2,\ldots,a_{100}

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

n

，使得

n

的任何倍数都不是 fancy 数。

第 3/5 步：小指数情形与结论

上一步下一步

a_r\le100\Longrightarrow cn\le2^0+2^1+\cdots+2^{100}=n

详细分析

若 $a_r\le100$ ，则二进制展开至多使用从 $\{2^0,2^1,\ldots,2^{100}\}$ 中选出的 $100$ 个二的幂。因此 $cn\le2^0+2^1+\cdots+2^{100}=n$ 。由于 $cn$ 是 $n$ 的正倍数，取等将迫使 $c=1$ ，并要求 $2^0,\ldots,2^{100}$ 这 $101$ 个二的幂全部出现；但表示至多使用 $100$ 个二的幂，这是不可能的。此矛盾说明 $n=2^{101}-1$ 的任何正倍数都不是 fancy；结合下界，得到这是最小的此类整数。