5
$\begingroup$

A friend of mine recently asked me this question.

For a positive integer $n$, a function $f(n)$ is defined as:

$f(n)=$ sum of digits in $n$.

given $f(n)=5$ find the maximum value of $f(n^5)$.

I tried solving this problem by putting random values, but my friend gave me a hint that the answer is greater than 100. Now I am completely lost because I couldn't find a single $n$ for which the value of $f(n^5)$ comes out to be greater than 100. Is there a proper way to solve it?

$\endgroup$
  • $\begingroup$ Quick search turned up $20111$ for which $f(n^5)=101$. $\endgroup$ – lulu Apr 7 '17 at 20:01
  • $\begingroup$ Oh, you can get higher by looking at $20^k111$ for various $k$. Not sure how to find the max... $\endgroup$ – lulu Apr 7 '17 at 20:02
  • $\begingroup$ That's great @lulu but even if I come up with a number, I won't be able to show that it's the max. $\endgroup$ – aroma Apr 7 '17 at 20:04
  • 2
    $\begingroup$ Consider a decimal number of the form $10 \cdots 0010 \cdots 0010 \cdots 0010 \cdots 001$ ... now think about $(1+a+b+c+d)^5$ where $a,b,c$ & $d$ are powers of 10 ... the anwer will be $5^5=3125$ ... full solution on request ... if further explanation required. $\endgroup$ – Donald Splutterwit Apr 7 '17 at 20:05
  • $\begingroup$ But how do we prove that 3125 is the maximum it would ever achieve? What about the case when it is something like 20..0010..0010..00100. $\endgroup$ – aroma Apr 7 '17 at 20:08
5
$\begingroup$

$f(xy) \le f(x) f(y)$, with equality only if there are no carries in the long multiplication of $x$ and $y$. So $f(n^5) \le f(n)^5 = 5^5$, with equality only if there are no carries. Well, you can't quite get away with no carries because ${5 \choose 2} = {5 \choose 3} = 10$, but you can try to reduce them. For example,

$f(1 + 10^2 + 10^{12} + 10^{62} + 10^{216}) = 5$ and $f((1 + 10^2 + 10^{12} + 10^{62} + 10^{216})^5) = 398$

I think this is the best possible.

$\endgroup$
  • $\begingroup$ I believe you're right that 398 is the max. $\endgroup$ – browngreen Apr 7 '17 at 20:52
  • $\begingroup$ I didn't understand the part when you said, "you can't get away with carry because ${5 \choose 2} = {5 \choose 3} = 10$". What does ${5 \choose 2}$ mean in here? $\endgroup$ – aroma Apr 8 '17 at 9:16
  • $\begingroup$ can you explain that?^ $\endgroup$ – aroma Apr 19 '17 at 15:56
  • $\begingroup$ There has to be at least one carry because if $n$ has at least two nonzero digits $a$ and $b$, when expanding $n^5$ using the binomial theorem you get a term ${5 \choose 2} a^2 b^3$ times a power of $10$, and thus when adding the terms with $a^2 b^3$ you get at least one carry. $\endgroup$ – Robert Israel Apr 19 '17 at 19:58
0
$\begingroup$

Consider the terms generated by $(a+b+c+d+e)^5$. There will be $5$ of the form $a^5$ which will have a coeffiecient of $1$ & each will therefore give a contribution of $1$, there will be $20$ of the form $a^4 b$ which will have a coeffiecient of $5$ & will therefore give a contribution of $5$, etc ... terms whose coefficients are a multiple of $10$ will only give that multiple. The following table summarises the possible contributions

\begin{eqnarray*} \begin{array}{|c|c|c|c|c|} \hline form & multiplicity & coefficient & contribution & tot \\ \hline a^5 & 5 & 1 & 1 & 5 \\ \hline a^4b & 20 & 5 & 5 & 100 \\ \hline a^3b^2 & 20 & 10 & 1 & 20 \\ \hline a^3bc & 30 & 20 & 2 & 60 \\ \hline a^2b^2c & 30 & 30 & 3 & 90 \\ \hline a^2bcd & 20 & 60 & 6 & 120 \\ \hline abcde & 1 & 120 & 3 & 3 \\ \hline \end{array} \end{eqnarray*}

Totting up the tot ... we make the best $f(n^5)=\color{red}{398}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.