Problem:
The sequence (an) is defined recursively by a0=1,a1=192, and an=an−1an−22 for n≥2. What is the smallest positive integer k such that the product a1a2⋯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 a1a2⋯ak is an integer if and only if ∑i=1kbi is divisible by 19. Let cn=bnmod19. It follows that a1a2⋯ak is an integer if and only if pk=∑i=1kci is divisible by 19 . Let qk=pkmod19. 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=a1a2⋯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.)