Skip to main content
OlympiadHQ

Browse · harp

Print

smc

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