2016 AMC 12B Problems/Problem 25
The sequence is defined recursively by , , and for . What is the smallest positive integer such that the product is an integer?
Let . Then and for all . The characteristic polynomial of this linear recurrence is , which has roots and .
Therefore, for constants to be determined . Using the fact that we can solve a pair of linear equations for :
Thus , , and .
Now, , so we are looking for the least value of so that
Note that we can multiply all by three for convenience, as the are always integers, and it does not affect divisibility by .
Now, for all even the sum (adjusted by a factor of three) is . The smallest for which this is a multiple of is by Fermat's Little Theorem, as it is seen with further testing that is a primitive root .
Now, assume is odd. Then the sum (again adjusted by a factor of three) is . The smallest for which this is a multiple of is , by the same reasons. Thus, the minimal value of is .
Since the product is an integer, it must be a power of , so the sum of the base- logarithms must be an integer. Multiply all of these logarithms by (to make them integers), so the sum must be a multiple of .
The logarithms are . Using the recursion (modulo to save calculation time), we get the sequence Listing the numbers out is expedited if you notice .
The cycle repeats every terms. Notice that since , the first terms sum up to a multiple of . Since , we only need at most the first terms to sum up to a multiple of , and this is the lowest answer choice.
Note: To rigorously prove this is the smallest value, you will have to keep a running sum of the terms and check that it is never a multiple of before the th term.
Like in Solution 2, calculate the first few terms of the sequence, but also keep a running sum of the logarithms (not modulo here): Notice that for odd and for even . Since is relatively prime to , we can ignore even and calculate odd using (modulo ): is first a multiple of at . ~emerald_block
|2016 AMC 12B (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25|
|All AMC 12 Problems and Solutions|