Difference between revisions of "2016 AMC 12B Problems/Problem 25"
(→Solution) |
(→Solution 2) |
||
Line 31: | Line 31: | ||
− | <math>a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12}a_{13}a_{14}a_{15}a_{16}a_{17}=2^{87381/19}=2^{4599}\approx 2.735\cdot 10{1384}</math> | + | <math>a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12}a_{13}a_{14}a_{15}a_{16}a_{17}=2^{87381/19}=2^{4599}\approx 2.735\cdot 10^{1384}</math> |
==See Also== | ==See Also== | ||
{{AMC12 box|year=2016|ab=B|after=Last Problem|num-b=24}} | {{AMC12 box|year=2016|ab=B|after=Last Problem|num-b=24}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 20:45, 21 February 2016
Contents
Problem
The sequence is defined recursively by , , and for . What is the smallest positive integer such that the product is an integer?
Solution 1
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 .
Solution 2
Since the product is an integer, the sum of the logarithms must be an integer. Multiply all of these logarithms by , so that the sum must be a multiple of . We take these vales modulo to save calculation time. Using the recursion : Notice that . The cycle repeats every terms. Since and , we only need the first terms to sum up to a multiple of : .
See Also
2016 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 24 |
Followed by Last Problem |
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.