2014 AIME II 第 15 题

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

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

15.

对任意整数 k1k \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 = 1xn+1X(xn)=xnp(xn)x_{n+1} X(x_n) = x_n p(x_n)n0n \ge 0)定义。求满足 xt=2090x_t = 2090 的最小正整数 tt

For any integer k1,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 n0.n \ge 0. Find the smallest positive integer tt such that xt=2090.x_t = 2090.

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

按顺序列出素数为 ρ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ρj1X(x_n) = \rho_0 \rho_1 \cdots \rho_{j-1},这正是对应末尾 11 位的素数乘积(当 j=0j = 0X(xn)=1X(x_n) = 1)。所以 xn+1=xnρjρ0ρ1ρj1x_{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=251119=ρ0ρ2ρ4ρ72090 = 2 \cdot 5 \cdot 11 \cdot 19 = \rho_0 \rho_2 \rho_4 \rho_7,对应二进制表示中位置 00224477 上的数字为一。因此 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ρj1X(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ρj1x_{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=251119=ρ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 题