2004 AIME I Problems/Problem 15
For all positive integers , let and define a sequence as follows: and for all positive integers . Let be the smallest such that . (For example, and .) Let be the number of positive integers such that . Find the sum of the distinct prime factors of .
We backcount the number of ways. Namely, we start at , which can only be reached if , and then we perform operations that either consist of or . We represent these operations in a string format, starting with the operation that sends and so forth downwards. There are ways to pick the first operations; however, not all of them may be otherwise we return back to , contradicting our assumption that was the smallest value of . Using complementary counting, we see that there are only ways.
Since we performed the operation at least once in the first operations, it follows that , so that we no longer have to worry about reaching again. Thus the remaining operations can be picked in ways, with a total of strings.
However, we must also account for a sequence of or more s in a row, because that implies that at least one of those numbers was divisible by , yet the was never used, contradiction. We must use complementary counting again by determining the number of strings of s of length such that there are s in a row. The first ten are not included since we already accounted for that scenario above, so our string of s must be preceded by a . There are no other restrictions on the remaining seven characters. Letting to denote either of the functions, and to indicate that the character appears times in a row, then our bad strings can take the forms:
There are ways to select the operations for the s, and places to place our block. Thus, our answer is , and the answer is .
|2004 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|