Sum of digits

First, we will make an observation. Suppose $a, b$ are positive integers. Then $S(a+b)$ can be computed from $S(a), S(b)$ , and the number of carries in $a+b$ . Indeed, if there is no carry, then it's easy to see that $S(a+b) = S(a) + S(b)$ . However, each carry will cause $S(a+b)$ to decrease by 9; that's how much is lost by subtracting 10 from a "digit" and adding 1 to the next more significant digit. Thus if $S(a), S(b)$ are fixed and we want to maximize $S(a+b)$ , we need to minimize the number of carries in $a+b$ .

If we want to make this formal, let $N$ be large enough; let $a = \sum_{n=0}^N a_n 10^n$ , and similarly $b = \sum_{n=0}^N b_n 10^n$ and $c = a+b = \sum_{n=0}^N c_n 10^n$ , where $0 \le a_n, b_n, c_n \le 9$ . (By picking $N$ large enough we can always do this. Some of the high-index digits may be zero, equivalent to padding zeroes to the left of the numbers.) Let $d_n$ indicate whether there is a carry when adding $a_n + b_n$ ; formally, $d_0 = 0$ (no carry on rightmost column), and for $1 \le n \le N$ , $d_n = 1$ if and only if $a_{n-1} + b_{n-1} + d_{n-1} \ge 10$ (which indicates there is a carry). If we're doing columnar addition like this , $a_n, b_n, c_n, d_n$ represents the first addend row, the second addend row, the result row, and the carry row, respectively.

Now, $S(a) = \sum a_n, S(b) = \sum b_n, S(a+b) = \sum c_n$ . But $c_n$ is defined as follows; if $a_{n-1} + b_{n-1} + d_{n-1} < 10$ , then $c_n = a_{n-1} + b_{n-1} + d_{n-1}$ , otherwise $c_n = a_{n-1} + b_{n-1} + d_{n-1} - 10$ . But this is coded in the definition of $d_n$ ; if $a_{n-1} + b_{n-1} + d_{n-1} < 10$ , then $d_n = 0$ , else $d_n = 1$ . Thus we can write $c_n = a_{n-1} + b_{n-1} + d_{n-1} - 10 d_n$ . So $S(a+b) = \sum (a_{n-1} + b_{n-1} + d_{n-1} - 10 d_n) = \sum a_n + \sum b_n - 9 \sum d_n$ , showing that each carry reduces $S(a+b)$ by 9.

---

Now to the problem. Since $S(n) = 4$ , we can represent $n = 10^a + 10^b + 10^c + 10^d$ for nonnegative integers $a, b, c, d$ ; we may assume $a \le b \le c \le d$ . Then

$\displaystyle n^4 = \sum_{p,q,r,s \in \{a,b,c,d\}} 10^{p+q+r+s}$

Grouping like terms, we have

$\displaystyle n^4 = \sum_{p,q,r,s} c_{p,q,r,s} \cdot 10^{p+q+r+s}$

where $p,q,r,s \in \{a,b,c,d\}$ , $p \le q \le r \le s$ , and $c_{p,q,r,s}$ is a coefficient depending on $p,q,r,s$ to be determined later.

Here we can already see that $n^4$ is the sum of several terms, more precisely $c_{p,q,r,s} \cdot 10^{p+q+r+s}$ among all possible $p,q,r,s$ . Each individual term has a fixed sum of digits, namely $S(c_{p,q,r,s})$ (which, since it depends only on $p,q,r,s$ , is fixed when $p,q,r,s$ are fixed; note that $10^{p+q+r+s}$ just pads zeroes to the right and don't contribute to the sum of digits). Thus to maximize $S(n^4)$ , by the above observation, we want to make as few carries as possible. As it turns out, we can pick $a,b,c,d$ to make sure none of these terms are even remotely close to interact, which means $S(n^4)$ is just the sum of $S(c_{p,q,r,s})$ .

First, we need to figure out what is $c_{p,q,r,s}$ . This is actually easy; if we fix $p,q,r,s$ , we're counting the coefficient of $10^{p+q+r+s}$ . This is given by multinomial theorem. For example, if $p = a, q = a, r = b, s = c$ , then we're finding the coefficient of $10^{2a+b+c}$ , which is given by the multinomial coefficient $\binom{4}{2,1,1} = \frac{4!}{2! 1! 1!} = 12$ . We can see that the largest $c_{p,q,r,s}$ is achieved when $p = a, q = b, r = c, s = d$ , giving a coefficient of 24.

So, in fact, if we can make sure that $p+q+r+s$ differs by at least 2 for different choices of $p,q,r,s$ , we can make sure that the terms $c_{p,q,r,s} \cdot 10^{p+q+r+s}$ don't interact and thus don't give any carry when added together. This can be achieved by, for example, picking $a = 10^0, b = 10^1, c = 10^2, d = 10^3$ ; the proof is left to the reader.

Now, we know that $S(n^4) = \sum S(c_{p,q,r,s})$ . We just need to find the values of $c_{p,q,r,s}$ and find the sum of the digits of each. This is where it gets messy, but at least we can simplify this into just five cases:

• If all of $p,q,r,s$ are the same, the coefficient is $\binom{4}{4} = 1$ . There are 4 choices of $p,q,r,s$ that lead to this case (all of them equal to one of $a, b, c, d$ ).
• If three of $p,q,r,s$ are the same and the other is different, the coefficient is $\binom{4}{3,1} = 4$ . There are 12 such choices: 4 ways to pick the triple, and 3 ways to pick the singleton.
• If they come in two pairs, the coefficient is $\binom{4}{2,2} = 6$ , and there are 6 such choices. (4 ways to pick the first pair, 3 ways to pick the second pair, divided by 2 for being able to switch them around.)
• If two are equal and the remaining two are different, the coefficient is $\binom{4}{2,1,1} = 12$ , and there are 12 such choices. (4 ways to pick the pair, 3 ways to pick the unchosen number.)
• If all are different, the coefficient is $\binom{4}{1,1,1,1} = 24$ , and there is 1 such choice.

Thus, we can see that in the fourth case above, we lose 9 due to carry ( $c_{p,q,r,s} = 12$ but $S(c_{p,q,r,s}) = 3$ ), and there are 12 coefficients that fall to the fourth case, so in total we lose 108 due to carry. The last case loses 18 more due to carry. In total, we lose 126 due to carries in the coefficients. This is the best we can do.

But we can easily compute $\sum c_{p,q,r,s}$ . This is simply $4^4 = 256$ : we pick a term from $10^a + 10^b + 10^c + 10^d$ in each factor of $n^4 = n \cdot n \cdot n \cdot n$ . There are 4 ways to pick a term, and 4 terms in total, so we have $4^4 = 256$ ways. Each way of picking the terms contributes exactly 1 to $\sum c_{p,q,r,s}$ , by definition of them being coefficients. So $\sum c_{p,q,r,s} = 256$ . Since we lose 126 due to carry, we have $\sum S(c_{p,q,r,s}) = 130$ , so $\max S(n^4) = \boxed{130}$ .

---

A variant of this problem, giving $S(n) = 5$ and asking for $S\big(n^5\big)$ , was given for the city qualifiers for Indonesian National Science Olympiad in Mathematics.

I simplified the problem so that we only have 5 cases. If the sum is 5, we have 7 cases to go through. (5 is also the number of partitions of 4, and 7 is the number of partitions of 5; this is not a coincidence.)

My solution was essentially the same as Ivan's, but I try to keep the argument more informal/intuitive, less symbolic/rigorous.

We can think of the number $n$ as being built by adding "ones". For instance, we could write $3010 = 1\cdot 10^3 + 1\cdot 10^3 + 1\cdot 10^3 + 1\cdot 10^1;$ because $S(n) = 4$ , there must be four of these terms. In other words, $n = 10^{a_1} + 10^{a_2} + 10^{a_3} + 10^{a_4},$ with the $a_i$ possibly different, possibly the same. Taking the fourth power produces $n^4 = 10^{a_i+a_j+a_k+a_\ell} + \cdots$ where $(i,j,k,\ell) = (1,1,1,1);\ (1,1,1,2);\ (1,1,1,3);\ \dots\ (4,4,4,3);\ (4,4,4,4)$ runs through all 256 possible ordered 4-tuples of indices 1,2,3,4.

In principle, each of these 256 terms contributes one to the sum of digits-- unless ten or more terms utilize the same power of 10. By way of illustration, $S(8 \times 10^5) = S(80000) = 8,\ \ \ \text{but}\ \ \ S(13\times 10^5) = S(130000) = 4\ \text{rather than}\ 13.$ Each time a digit "overflows" because it is used ten or more times, the digit sum decreases by nine... Therefore, in order to maximize $S(n^4)$ we wish to minimize this overflow. This can be accomplished by choosing the power $a_i$ of very different magnitudes. For instance, $n = 10^0 + 10^2 + 10^{10} + 10^{50} = 10\dots 010000000101$ works well, because each possible value of $a_i+a_j+a_k+a_\ell$ corresponds to a unique choice of $(i,j,k,\ell)$ up to permutation.

That inevitable "up to permutation" is precisely why we cannot make $S(n^4)$ equal to 256. Out of our 256 terms $10^{a_i+a_j+a_k+a_\ell}$ there will always be several equal to each other. We investigate by splitting out all possibilities. In the following, $p,q,r,s$ stand for four different indices chosen from $\{1,2,3,4\}$ .

• $(i,j,k,\ell) = (p,p,p,p)$ . There are four possible values $p = 1, \dots, 4$ , and for each only one possible permutations. In the ideal case, this contributes four times 1 to the digit sum.
• $(i,j,k,\ell) = (p,p,p,q)$ etc. There are twelve possible values for $p,q$ , and for each four possible permutations: $(p,p,p,q), (p,p,q,p), (p,q,p,p), (q,p,p,p)$ . Therefore we get twelve contributions of 4 to the digit sum.
• $(i,j,k,\ell) = (p,p,q,q)$ etc. There are six possible values for $\{p,q\}$ , and for each six possible permutations. Therefore we get six contributions of 6 to the digit sum.
• $(i,j,k,\ell) = (p,p,q,r)$ etc. There are twelve possible values for $p,s$ ( $s$ being the unused index), and for each twelve possible permutations. Thus there will be twelve contributions of $12\times 10^{2a_p+a_q+a_r}$ to $n^4$ . There is "overflow"; instead of contributing $12$ to the digit sum, this only contributes $3$ to the digit sum, twelve times.
• $(i,j,k,\ell) = (p,q,r,s)$ etc. There is one possible choice $\{p,q,r,s\} = \{1,2,3,4\}$ but there are 24 permutations. Thus there is a contribution of $24\times 10^{a_1+a_2+a_3+a_4}$ to $n^4$ . Again, there is "overflow"; instead of contributing $24$ to the digit sum, we only contribute $6$ .

Thus the digit sum will be, in the ideal case of no further overlap/overflow, $S(n^4) = 4\times 1 + 12\times 4 + 6\times 6 + 12\times 3 + 1\times 6 = \boxed{130}.$ (Note in contrast that without overflow, we would have $4\times 1 + 12\times 4 + 6\times 6 + 12\times 12 + 1\times 24 = 256.)$

With the concrete values mentioned above, we have as explicit example $n = 1\,0000000000\,0000000000\,0000000000\,0000000001\,0000000101;$ $n^4 = 1\,0000000000\,0000000000\,0000000000\,0000000004\,0000000404 \\ 0000000000\,0000000000\,0000000006\,0000001212\,0000061206 \\ 0000000000\,0000000004\,0000001212\,0000122412\,0004121204 \\ 0000000001\,0000000404\,0000061206\,0004121204\,0104060401.$

if n=100....010...0100.....01 , wouldnt that make n^4 has 256 1s and alot of 0s?