Find sod ( sod ( sod (4444 ^ 4444 ) ) ).

Amazingly, the answer can be found with a normal calculator.  Let X be
4444^4444, and Y = sod(sod(sod(X))).

Let's calculate Y's remainder upon division by 9.  It is a well-known fact
that n == sod(n) (mod 9) for all positive numbers.  Therefore, Y == X (mod
9).  4444 == 7 (mod 9), so Y == X == 7^4444 (mod 9).  We also discover that
7^3 == 1 (mod 9), so 7^4444 = 7 * (7^3)^1481 == 7 (mod 9).  Therefore,

Y == 7 (mod 9) (*)

Furthermore,

X < 10000^4444 = (10^4)^4444 = 10^(4*4444) = 10^17776.

Of all numbers less than 10^17776, the one with the highest total digital
sum is 10^17776-1, i.e. 17776 9's.  Therefore, sod(X) <= 9 * 17776 =
159984.  Similarly, sod(sod(X)) <= sod(99999) = 45, and we do it again to get:

Y <= sod(39) = 12  (**) 

The only positive number that satisfies both (*) and (**) is 7, so
sod(sod(sod(4444^4444))) = 7.

Matthew Daly
mwdaly@kodak.com