2014 AIME II Problems/Problem 15
For any integer , let be the smallest prime which does not divide Define the integer function to be the product of all primes less than if , and if Let be the sequence defined by , and for Find the smallest positive integer such that
Note that for any , for any prime , . This provides motivation to translate into a binary sequence .
Let the prime factorization of be written as , where is the th prime number. Then, for every in the prime factorization of , place a in the th digit of . This will result in the conversion .
Multiplication for the sequence will translate to addition for the sequence . Thus, we see that translates into . Since , and , corresponds to , which is in binary. Since , = .
Solution 2 (Painful Bash)
We go through the terms and look for a pattern. We find that
Commit to the bash. Eventually, you will receive that , so is the answer. Trust me, this is worth the 10 index points.
Solution 3 (induction)
Let denote the th prime. Lemma: for all [b]Proof:[/b] We can prove this using induction. Assume that Then, using the given recursion , we would “start fresh” for It is then easy to see that then just cycles through the previous terms of since the recursion process is the same and being a factor of is not affected until when given our assumption and is now the least such that in which where is the only way that the aforementioned cycle would be affected. Specifically, by cancellation according to our recursion, and the values of just starts cycling through the previous terms again until when a new prime shows up in the prime factorization of when it starts cycling again, and so on. Using our base cases of and our induction is complete. Now, it is easy to see that and by Lemma #1, the least positive integer such that is By repeatedly applying our obtained recursion from Lemma #1, it is easy to see that our answer is just or
|2014 AIME II (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|