第2题

若正整数可写成

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

的形式（其中

a_1,a_2,\ldots,a_{100}

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

n

，使得

n

的任何倍数都不是 fancy 数。

第 4/5 步：极小反例中的大指数情形

上一步下一步

cn=2^{a_1}+\cdots+2^{a_r},\ r\le100,\ a_r\ge101\Longrightarrow 2^{a_r}=2^{a_r-101}n+2^{a_r-101}

详细分析

反设 $n=2^{101}-1$ 的某个倍数 $cn$ 是 fancy 数。将重复的二的幂按二进制进位合并，可得到至多 $100$ 个互异二的幂的表示；在这些表示中取 $c$ 最小，并设最大指数为 $a_r$ 。若 $a_r\ge101$ ，则 $2^{a_r}=2^{a_r-101}n+2^{a_r-101}$ ，于是把 $2^{a_r}$ 换成 $2^{a_r-101}$ 会使 $cn$ 减少 $2^{a_r-101}n$ ，得到一个仍只含至多 $100$ 个二的幂的 $n$ 的更小正倍数，与 $c$ 的最小性矛盾。