[문제 풀이] 자릿수의 합

${4444}^{4444}$의 각 자릿수의 합을 $A$, $A$의 각 자릿수의 합을 $B$라 할 때, $B$의 각 자릿수의 합을 구하시오.

---

주어진 자연수의 각 자릿수를 더해서 나온 수에 대해 다시 각 자릿수를 더하는 것을 계속 반복하면, 결국 1에서 9까지의 자연수 중 하나가 나오죠. 그럼 이 수는 어떤 수가 될까요?

이건 9의 배수의 성질을 가지고 생각할 수 있는 문제예요.

십진법으로 표현된 $n$자리 자연수는$${10}^{n-1}{d}_{n-1}+{10}^{n-2}{d}_{n-2}+\cdots +{10}^0{d}_0$$이라고 표현할 수 있어요. 각 ${10}^k$의 자리가 $d_k$인 거죠. 각 자릿수의 합 $d_{n-1}+d_{n-2}+\cdots +d_0$를 비교하면 그 차가$$\stackrel{n-2}{\overbrace{99\cdots 9}}{d}_{n-1}+\stackrel{n-3}{\overbrace{99\cdots 9}}{d}_{n-2}+\cdots +9d_1$$로 9의 배수이니 두 수를 9로 나눈 나머지가 같아요. 즉, 자릿수의 합을 반복하면 나오는 한 자리 자연수는 주어진 자연수를 9로 나눈 나머지 $r$가 0이 아니라면 $r$이고, $r=0$이면 9가 되는 거죠.

이제 주어진 자연수 ${4444}^{4444}$에서 자릿수의 합을 세 번 시행하면 몇 자리 자연수가 나오는지 확인해야 겠네요.

${4444}^{4444}<{10000}^{4444}={10}^{17776}$이니 17776 이하가 되겠죠. 즉, $A<9\cdot 17776=159984$가 성립해요. 159984보다 작은 자연수 중 자릿수의 합이 가장 큰 수는 99999이니 $B\le 45$라는 걸 알 수 있죠. 45 이하의 자연수 중 자릿수의 합이 가장 큰 수는 39로 $B$의 각 자릿수의 합은 12 이하겠네요.

$4444\equiv 7(\mathrm{mod}9),7^3\equiv (-2{)}^3=-8\equiv 1(\mathrm{mod}9)$에서$${4444}^{4444}\equiv 7^{4444}\equiv 7(\mathrm{mod}9)$$가 성립하고, 12 이하의 자연수 중 9로 나눈 나머지가 7인 수는 7이 유일하니 구하고자 하는 수는 7이라는 걸 알 수 있죠.

---

물론 이런 문제에 진법을 바꿔 생각할 수도 있어요. $n$진법에서 생각한다면 $n-1$로 나눈 나머지를 생각하는 거죠.