Digit Sums of Exponentiated Numbers

The key to the solution is to realize that digit sums are conserved under modular arithmetic mod $9$ . This means that $S_k(n)\equiv n^k \text{ (mod } 9 )$ . Let's make a chart for $n^k$ (mod $9$ ) for the first few values of $k$ .

As you can see, the pattern repeats after every multiple of $6$ , so we only need to consider the first $6$ values of $k$ , a

$k\equiv1\text{ (mod } 6 )$ :

Here, we can see from the chart that if $n$ is coprime to $9$ , then $S_k(n)\equiv n\text{ (mod } 9 )$ , therefore we must have at least $7$ sets in $U_k$ , and $U_k$ must have the following form (mod $9$ ):

$\{[0],[1],[2],[4],[5],[7],[8]\}\Longrightarrow \text{If } k\equiv2\text{ (mod } 6 )\text{, Minimum = }7$

$k\equiv2\text{ (mod } 6 )$ :

Here, $S_k(n)$ can only be $0$ , $1$ , $4$ , or $7$ (mod $9$ ). We can also see that if $n\equiv4\text{ (mod } 6 )$ then $S_k(n)\equiv7\text{ (mod } 6 )$ , and if $n\equiv7\text{ (mod } 6 )$ then $S_k(n)\equiv4\text{ (mod } 6 )$ , so we have the possible configuration for $U_k$ :

$\{[0],[1],[4,7]\}\Longrightarrow \text{If } k\equiv2\text{ (mod } 6 )\text{, Minimum = }3$

$k\equiv3\text{ (mod } 6 )$ :

The chart shows that $S_k(n)\in\{0,1,8\}$ , and each number maps to itself under the function $S_k(n)$ , meaning that $U_k$ has the form:

$\{[0],[1],[8]\}\Longrightarrow \text{If } k\equiv2\text{ (mod } 6 )\text{, Minimum = }3$

$k\equiv4\text{ (mod } 6 )$ :

This configuration is nearly identical to when $k\equiv2\text{ (mod } 6 )$ . The only possibilities for $S_k(n)$ are $0$ , $1$ , $4$ , or $7$ (mod $9$ ), $0$ and $1$ map to themselves, $4$ maps to $7$ and $7$ maps back to $4$ , giving us the possible arrangement for $U_k$ :

$\{[0],[1],[4,7]\}\Longrightarrow \text{If } k\equiv2\text{ (mod } 6 )\text{, Minimum = }3$

$k\equiv5\text{ (mod } 6 )$ :

Like when $k\equiv1\text{ (mod } 6 )$ , $S_k(n)$ can assume the values $0$ , $1$ , $2$ , $4$ , $5$ , $7$ or $8$ (mod $9$ ). Unlike when $k\equiv1\text{ (mod } 6 )$ , not all the numbers map to themselves under $S_k(n)$ . $0$ , $1$ and $8$ map to themselves, while $2$ and $5$ form a pair, as well as $4$ and $7$ . This leads to the following configuration of $U_k$ :

$\{[0],[1],[8],[2,5],[4,7]\}\Longrightarrow \text{If } k\equiv2\text{ (mod } 6 )\text{, Minimum = }5$

$k\equiv0\text{ (mod } 6 )$ :

It's easy to see that this will be our minimum. $S_k(n)$ can only have the values $0$ and $1$ , and each number maps to itself, leading to the minimum configuration for $U_k$ :

$\{[0],[1]\}\Longrightarrow \text{If } k\equiv2\text{ (mod } 6 )\text{, Minimum = }2$

As you can see, when $k\equiv0\text{ (mod } 6 )$ , $U_k$ can contain a minimum of just $2$ sets, where as for other values of $k$ it must contain more, therefore our final answer must be $\boxed{2}$ .

Note: a lot of these congruences can also be proven by using Euler's Theorem, $n^{\phi(a)m} \equiv 1 \text{ (mod } a )$ , where $n$ , $m$ and $a$ are positive integers, $n$ and $a$ are coprime and $\phi(a)$ is the Euler totient function. Setting $a=9$ , $\phi(9)=6$ , therefore we have the congruence $n^{6m} \equiv 1 \text{ (mod } 9 )$ , which can be seen in our minimum solution above.