Browse · harp
Printsmc
number theory senior
Problem
Let denote the number of positive integers that divide , including and . For example, and . (This function is known as the divisor function.) LetThere is a unique positive integer such that for all positive integers . What is the sum of the digits of
(A)
(B)
(C)
(D)
(E)
Solution
We consider the prime factorization of By the Multiplication Principle, we have Now, we rewrite as As for all positive integers note that if and only if for all positive integers and So, is maximized if and only if is maximized. For each independent factor with a fixed prime where the denominator grows faster than the numerator, as exponential functions always grow faster than polynomial functions. Therefore, for each prime with we look for the nonnegative integer such that is a relative maximum: \begin{array}{c|c|c|c|c} & & & & \\ [-2.25ex] \boldsymbol{i} & \boldsymbol{p_i} & \boldsymbol{e_i} & \boldsymbol{\dfrac{(e_i+1)^3}{p_i^{e_i}}} & \textbf{Max?} \\ [2.5ex] \hline\hline & & & & \\ [-2ex] 1 & 2 & 0 & 1 & \\ & & 1 & 4 & \\ & & 2 & 27/4 &\\ & & 3 & 8 & \checkmark\\ & & 4 & 125/16 & \\ [0.5ex] \hline & & & & \\ [-2ex] 2 & 3 & 0 & 1 &\\ & & 1 & 8/3 & \\ & & 2 & 3 & \checkmark\\ & & 3 & 64/27 & \\ [0.5ex] \hline & & & & \\ [-2ex] 3 & 5 & 0 & 1 & \\ & & 1 & 8/5 & \checkmark\\ & & 2 & 27/25 & \\ [0.5ex] \hline & & & & \\ [-2ex] 4 & 7 & 0 & 1 & \\ & & 1 & 8/7 & \checkmark\\ & & 2 & 27/49 & \\ [0.5ex] \hline & & & & \\ [-2ex] \geq5 & \geq11 & 0 & 1 & \checkmark \\ & & \geq1 & \leq8/11 & \\ [0.5ex] \end{array} Finally, the positive integer we seek is The sum of its digits is Alternatively, once we notice that is a factor of we can conclude that the sum of the digits of must be a multiple of Only choice is possible.
Final answer
E