Given $f(n)$ how to find the maximum value of $f(n^5)$?

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?

• Quick search turned up $20111$ for which $f(n^5)=101$. – lulu Apr 7 '17 at 20:01
• Oh, you can get higher by looking at $20^k111$ for various $k$. Not sure how to find the max... – lulu Apr 7 '17 at 20:02
• 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. – aroma Apr 7 '17 at 20:04
• 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. – Donald Splutterwit Apr 7 '17 at 20:05
• 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. – aroma Apr 7 '17 at 20:08

$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.

• I believe you're right that 398 is the max. – browngreen Apr 7 '17 at 20:52
• 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? – aroma Apr 8 '17 at 9:16
• can you explain that?^ – aroma Apr 19 '17 at 15:56
• 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. – Robert Israel Apr 19 '17 at 19:58

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}$.