Problem:
The sequence (an​) is defined recursively by a0​=1,a1​=192​, and an​=an−1​an−22​ for n≥2. What is the smallest positive integer k such that the product a1​a2​⋯ak​ is an integer?
Answer Choices:
A. 17
B. 18
C. 19
D. 20
E. 21 Solution:
Express each term of the sequence (an​) as 219bn​​. (Equivalently, let bn​ be the logarithm of an​ to the base 192​.) The recursive definition of the
sequence (an​) translates into b0​=0,b1​=1, and bn​=bn−1​+2bn−2​ for n≥2. Then the product a1​a2​⋯ak​ is an integer if and only if ∑i=1k​bi​ is divisible by 19. Let cn​=bn​mod19. It follows that a1​a2​⋯ak​ is an integer if and only if pk​=∑i=1k​ci​ is divisible by 19 . Let qk​=pk​mod19. Because the largest answer choice is 21 , it suffices to compute ck​ and qk​ successively for k from 1 up to at most 21 , until qk​ first equals 0 . The modular computations are straightforward from the definitions.
Using standard techniques, the recurrence relation for bn​ can be solved to get bn​=31​(2n−(−1)n). Let Sk​=b1​+b2​+⋯+bk​. Then it is straightforward to show that Sk​=31​(2k+1−1) for k odd, and Sk​=32​(2k−1) for k even. Let Pk​=a1​a2​⋯ak​. It follows that, for k odd, Pk​ is an integer if and only if 19 divides 2k+1−1; and, for k even, Pk​ is an integer if and only if 19 divides 2k−1. A little computation shows that this first occurs at k=17, when 218−1=218−1=(29−1)(29+1)=511⋅513=511⋅19⋅27. (In fact, one can show that Pk​ is an integer if and only if k is congruent to 0 or −1mod18.)