2019 AIME II Problems/Problem 12
For call a finite sequence of positive integers progressive if and divides for all . Find the number of progressive sequences such that the sum of the terms in the sequence is equal to .
If the first term is , then dividing through by , we see that we can find the number of progressive sequences whose sum is , and whose first term is not 1. If denotes the number of progressive sequences whose sum is and whose first term is not 1, then we can express the answer as follows:
The at the end accounts for the sequence whose only term is 360. Fortunately, many of these numbers are prime; we have for primes as the only such sequence is "" itself. Also, . So we have
For small , is easy to compute: , , . For intermediate (e.g. below), can be computed recursively using previously-computed values of , similar to dynamic programming. Then we have Thus the answer is .
|2019 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|