Problem:
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 .
Solution:
We know that the sum of the terms of the sequence sum to 360.
Then, if the first term is , the sum of the rest of the sequences is
So, this problem is equivalent to finding the number of sequences that sum to yet all the following terms must also be divisible by x so it's also equivalent to finding the number of sequences that sum to where
Let's consider the factors of 360 to figure out the possible first terms.
If the first term is 1, we'd have to solve this problem from the second term starting from
If the first term is 2, then we have to solve this problem over
If the first term is 3, it'd be 119, and similarly for the rest of the possible first terms, it'd be 89, then 71, then 59, then 44, then 39, then 35, then 29, 23, 19, 17, 14, 11, 9, 8, 7, 5, 4, 3, 2, 1,
plus adding 1 at the end if the sequence is just
For prime numbers, this problem is very easy to solve as for example for , the only sequence that is possible is just
There are 14 primes, and then we have to figure out how to solve this problem over
119, 44, 39, 35, 14, 9, 8, and 4, reminding to add one for at the end.
For each of this, solve them the exact same way we reduced into for each factor x, and we get that if is the answer for the number k that
Thus, adding these all up, we'd have
and add 1 for to get
OLD SOLUTION
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 . If denotes the number of progressive sequences whose sum is and whose first term is not , then we can express the answer as follows:
The at the end accounts for the sequence whose only term is . 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 .
The problems on this page are the property of the MAA's American Mathematics Competitions