2014 AIME II Problem 15

Attempt Problem 15 of the 2014 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2014 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

15.

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.

Answer: 149
Concepts:primenumber baserecursionpattern recognition
Difficulty rating: 3270
Solution:

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.

← Problem 14#14
Full Exam

Problem 15 in Other Years