Question

求小于 $1000$ 且可以表示为两个 $2$ 的整数次幂之差的正整数个数。

Find the number of positive integers less than $1000$ that can be expressed as the difference of two integral powers of $2.$

答案

答案：50

知识点：2的幂因式分解分类讨论

难度评级：2110

小提示：

每个这样的差都可写成 $2^b(2^c - 1)$ ，其中 $c \ge 1$ ，并且它的奇数部分 $2^c - 1$ 会确定 $c$

Every such difference is $2^b(2^c - 1)$ with $c \ge 1,$ and its odd part $2^c - 1$ identifies $c$

大提示：

不同的数对 $(b, c)$ 给出不同的值，所以对每个 $c$ 分别统计小于 $1000$ 的值。注意： $63 \cdot 16 = 1008$ 会打破前面的模式。

Distinct pairs $(b, c)$ give distinct values, so count values below $1000$ for each $c$ separately. Beware: $63 \cdot 16 = 1008$ breaks the pattern.

解答：

两个 $2$ 的幂之差为 $2^a - 2^b = 2^b(2^c - 1)$ ，其中 $c = a - b \ge 1$ 。因为 $2^c - 1$ 是奇数，所以该数的奇数部分确定 $c$ ，而 $2$ 的幂次部分确定 $b$ ，因此不同的数对 $(b, c)$ 会给出不同整数。只需统计满足 $2^b(2^c - 1) \lt 1000$ 的数对。

对 $c = 1, 2, \ldots, 9$ ，因子 $2^c - 1$ 分别为 $1, 3, 7, 15, 31, 63, 127, 255, 511$ ，允许的 $b$ 的个数分别为 $10, 9, 8, 7, 6, 4, 3, 2, 1$ （ $63$ 的计数降为 $4$ ，因为 $63 \cdot 16 = 1008 \gt 1000$ ，而 $31 \cdot 32 = 992$ 仍然符合）。

总数为 $10 + 9 + 8 + 7 + 6$ $+ 4 + 3 + 2 + 1 = 50$ 。

A difference of powers of $2$ is $2^a - 2^b = 2^b(2^c - 1)$ where $c = a - b \ge 1.$ Since $2^c - 1$ is odd, the odd part of the number determines $c$ and the power of $2$ determines $b,$ so distinct pairs $(b, c)$ yield distinct integers. It suffices to count pairs with $2^b(2^c - 1) \lt 1000.$

For $c = 1, 2, \ldots, 9$ the factor $2^c - 1$ is $1, 3, 7, 15, 31, 63, 127, 255, 511,$ and the number of allowed values of $b$ is $10, 9, 8, 7, 6, 4, 3, 2, 1$ respectively (the count for $63$ drops to $4$ because $63 \cdot 16 = 1008 \gt 1000,$ while $31 \cdot 32 = 992$ still fits).

The total is $10 + 9 + 8 + 7 + 6$ $+ 4 + 3 + 2 + 1 = 50.$

2021 AIME I 第 3 题

答案：50

难度评级：2110

小提示：

大提示：

解答：

其他年份的第 3 题