2014 AIME II Problem 15

Below is the professionally curated solution for Problem 15 of the 2014 AIME II, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:primenumber baserecursionpattern recognition

Difficulty rating: 3270

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.

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 14Full Exam

Problem 15 in Other Years