2014 AIME II 第 15 题

先试着解答 2014 AIME II 第 15 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2014 AIME II 解答,或核对答案。

所有题目均经美国数学协会(MAA)官方合法授权使用。

15.

对任意整数 k≥1k \ge 1,令 p(k)p(k) 为不整除 kk 的最小素数。定义整数函数 X(k)X(k):若 p(k)>2p(k) \gt 2,则该函数值为所有小于 p(k)p(k) 的素数的乘积;若 p(k)=2p(k) = 2,则 X(k)=1X(k) = 1。设序列 {xn}\{x_n\} 由 x0=1x_0 = 1 和 xn+1X(xn)=xnp(xn)x_{n+1} X(x_n) = x_n p(x_n)(n≥0n \ge 0)定义。求满足 xt=2090x_t = 2090 的最小正整数 tt。

For any integer k≥1,k \ge 1, let p(k)p(k) be the smallest prime which does not divide k.k. Define the integer function X(k)X(k) to be the product of all primes less than p(k)p(k) if p(k)>2,p(k) \gt 2, and X(k)=1X(k) = 1 if p(k)=2.p(k) = 2. Let {xn}\{x_n\} be the sequence defined by x0=1,x_0 = 1, and xn+1X(xn)=xnp(xn)x_{n+1} X(x_n) = x_n p(x_n) for n≥0.n \ge 0. Find the smallest positive integer tt such that xt=2090.x_t = 2090.

答案:149
知识点:质数进制递推找规律
难度评级:3270
小提示:

计算 x1x_1 到 x8x_8 并分解质因数;比较 xnx_n 中出现的素数集合和 nn 的二进制数位。

Compute x1x_1 through x8x_8 and factor each; compare the set of primes appearing in xnx_n with the binary digits of nn

大提示:

这个递推就是二进制计数:除以 X(xn)X(x_n) 会清掉末尾为一的若干位,乘以 p(xn)p(x_n) 则把 11 进到下一位。

The recursion is binary counting: dividing by X(xn)X(x_n) clears the trailing prime “ones” and multiplying by p(xn)p(x_n) carries a 11 into the next bit

解答:

按顺序列出素数为 ρ0=2\rho_0 = 2、ρ1=3\rho_1 = 3、ρ2=5,…\rho_2 = 5, \ldots。每个 xnx_n 都是无平方因子的,所以它由整除它的素数集合决定。我们断言这个集合编码了 nn 的二进制表示:若 n=∑idi2in = \sum_i d_i 2^i,其中 di∈{0,1}d_i \in \{0, 1\},则 xn=∏iρidix_n = \prod_i \rho_i^{d_i}。

的确,假设 xn=∏iρidix_n = \prod_i \rho_i^{d_i},并令 jj 为使 dj=0d_j = 0 的最小下标。则 p(xn)=ρjp(x_n) = \rho_j,而 X(xn)=ρ0ρ1⋯ρj−1X(x_n) = \rho_0 \rho_1 \cdots \rho_{j-1},这正是对应末尾 11 位的素数乘积(当 j=0j = 0 时 X(xn)=1X(x_n) = 1)。所以 xn+1=xn ρjρ0ρ1⋯ρj−1x_{n+1} = \frac{x_n \, \rho_j}{\rho_0 \rho_1 \cdots \rho_{j-1}} 会去掉末尾的一串 11,并插入 ρj\rho_j,这正是二进制加一。因为 x0=1x_0 = 1 对应 00,归纳证明了断言。

现在 2090=2⋅5⋅11⋅19=ρ0ρ2ρ4ρ72090 = 2 \cdot 5 \cdot 11 \cdot 19 = \rho_0 \rho_2 \rho_4 \rho_7,对应二进制表示中位置 00、22、44、77 上的数字为一。因此 t=20+22+24+27=149t = 2^0 + 2^2 + 2^4 + 2^7 = 149。

List the primes in order as ρ0=2,\rho_0 = 2, ρ1=3,\rho_1 = 3, ρ2=5,….\rho_2 = 5, \ldots. Every xnx_n is squarefree, so it is described by the set of primes dividing it, and we claim this set encodes nn in binary: if n=∑idi2in = \sum_i d_i 2^i with di∈{0,1},d_i \in \{0, 1\}, then xn=∏iρidi.x_n = \prod_i \rho_i^{d_i}.

Indeed, suppose xn=∏iρidix_n = \prod_i \rho_i^{d_i} and let jj be the smallest index with dj=0.d_j = 0. Then p(xn)=ρj,p(x_n) = \rho_j, and X(xn)=ρ0ρ1⋯ρj−1X(x_n) = \rho_0 \rho_1 \cdots \rho_{j-1} is exactly the product of the primes for the trailing 11-bits (with X(xn)=1X(x_n) = 1 when j=0j = 0). So xn+1=xn ρjρ0ρ1⋯ρj−1x_{n+1} = \frac{x_n \, \rho_j}{\rho_0 \rho_1 \cdots \rho_{j-1}} removes the trailing ones and inserts ρj\rho_j — precisely adding 11 in binary. Since x0=1x_0 = 1 corresponds to 0,0, induction proves the claim.

Now 2090=2⋅5⋅11⋅19=ρ0ρ2ρ4ρ7,2090 = 2 \cdot 5 \cdot 11 \cdot 19 = \rho_0 \rho_2 \rho_4 \rho_7, which corresponds to binary digits at positions 0,0, 2,2, 4,4, 7.7. Hence t=20+22+24+27=149.t = 2^0 + 2^2 + 2^4 + 2^7 = 149.

第 14 题#14
完整试卷

其他年份的第 15 题