Question

Пусть S(n) — сумма цифр в десятичной записи числа n. Найдите S(S(S(S(2018^2017).

Answer 1

Итак, $n = 2018^{2017}$, а S(n) - это сумма цифр числа. Надо четыре раза подряд найти сумму цифр чисел, т.е. S(S(S(S(n)))).

Понятно, что невозможно сделать десятичную запись числа $2018^{2017}$.
Оценим, сколько  цифр м.б. в таком числе:

$n=2018^{2017}\ \textless \ 2048^{2017}=2^{11*2017}=2^{22187} \ \textless \ 2^{22191} =2^{13*1707} = \\ \\ = 8192^{1707} \ \textless \ 10^{4*1707} = 10^{6828}$

Итак, $n \ \textless \ 10^{6828}$

Если все цифры в числе будут 9, то их сумма будет не более, чем:
$S(n) \leq 9*6828=61452\ \textless \ 10^5$
Опять считаем суммы цифр. Пусть это будут девятки и их пять штук, то сумма не м.б. больше, чем:
$S(S(n)) \leq 9*5 \leq 45$
Максимальная сумма цифр м.б. только у числа 39 и она равна 12 (у числа 45 сумма всего 9):
$S(S(S(n))) \leq 3+9=12$
Наконец, приходим к выводу, что сумма не м.б. больше 9 (у числа 12 сумма цифр равна 3):
$S(S(S(S(n)))) \leq 9.$

Из всего выше изложенного стало ясно, что если в нашем числе $2018^{2017}$. четыре раза подряд просуммировать цифры, то результат не будет превышать 9!

Вроде бы ничего это нам не дала. Однако вспомним теорему об остатках при делении на 3 (или на 9). Остаток от деления числа на 3 (или на 9) равен остатку от деления на 3 (или на 9) его суммы цифр. Признак делимости на 3 (или на 9) в общем виде.
Теперь, зная это, мы можем найти остаток от деления числа $2018^{2017}$ на 9, тем самым мы узнаем, какой остаток будет от деления суммы цифр $S(S(S(S(n)))) \leq 9$ на 9. А это и будет ответ.

Представим число 2018 = 2016 + 2, как сумму двойки и числа 2016, которое делится на 9 без остатка. Затем (2016 + 2) возведём в степень 2017 и распишем результат в виде бинома Ньютона.
$2018^{2017}=(2016+2)^{2017} = \\ \\ = 2016^{2017} + C_{2017}^1 *2016^{2016} *2 + ... +2^{2017}$
Все слагаемые, кроме последнего $2^{2017}$, делятся на 9 без остатка (туда входит число 2016).

Преобразуем число $2^{2017}$, чтобы появилась 9, затем разложим по формуле бинома Ньютона:
$2^{2017} = 2*2^{2016} = 2 *2^{3*672} = 2*(2^3)^{672} = 2*(9-1)^{672}= \\ \\ 2*(9^{672}-C_{672}^1 * 9 * 1 + ... +1^{672}) = \\ \\ =2*9^{672}-2*C_{672}^1 * 9 * 1 + ... +2*1^{672} =$

В полученной сумме все слагаемые, кроме последнего, делятся на 9. А последнее слагаемой и есть остаток, и он равен 2.
Т.о. искомая сумма цифр равна:
$S(S(S(S(2018^{2017}) = 2$

Ответ: 2