[문제 풀이] 자릿수의 합

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

---

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

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

십진법으로 표현된 $n$자리 자연수는\[10^{n-1}d_{n-1}+10^{n-2}d_{n-2}+\cdots+10^0d_0\]이라고 표현할 수 있어요. 각 $10^k$의 자리가 $d_k$인 거죠. 각 자릿수의 합 $d_{n-1}+d_{n-2}+\cdots+d_0$를 비교하면 그 차가\[\overbrace{99\cdots9}^{n-2}d_{n-1}+\overbrace{99\cdots9}^{n-3}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\cdot17776=159984$가 성립해요. 159984보다 작은 자연수 중 자릿수의 합이 가장 큰 수는 99999이니 $B\le45$라는 걸 알 수 있죠. 45 이하의 자연수 중 자릿수의 합이 가장 큰 수는 39로 $B$의 각 자릿수의 합은 12 이하겠네요.

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

---

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