This Is Mental Math?!? Topic: Number Theory. Level: AIME.

Problem: (2006-2007 Warm-Up 2) Let $ f(x) $ be the sum of the digits of $ x $. Find $ f(f(f(8765^{4321}))) $.

Solution: Let's try bounding our quantity. We know

$ f(x) < 9 \cdot \lceil \log{x} \rceil $

because $ \lceil \log{x} \rceil $ is the number of digits of $ x $ (except when $ x $ is a power of ten, but those are trivial) and the biggest digit is $ 9 $. So we can say that

$ f(8765^{4321}) < 9 \cdot \lceil \log{8765^{4321}} \rceil < 9 \cdot \log{10000^{10000}} = 360000 $

so

$ f(f(8765^{4321})) < 9 \cdot \lceil \log{360000} \rceil < 9 \cdot \log{1000000} = 54 $

and

$ f(f(f(8765^{4321}))) < 13 $

because the largest sum of digits of any number less than $ 54 $ is $ 4+9 = 13 $. So we know our value is less than $ 13 $. But remember that the sum of the digits of a number is equal to itself $ \pmod{9} $ (prove this!) and $ 8765^{4321} \equiv (-1)^{4321} \equiv 8 \pmod{9} $ so our answer is also $ 8 \pmod{9} $. But the only number less than $ 13 $ that works is then $ 8 $. QED.

--------------------

Comment: Admittedly, this is not likely to show up on a mental math test, but it's feasible to do in your head. The bounding is not horrific and taking the mod is also not bad. Of course, $ 45 $ seconds is pretty quick, but if you knew how to approach the problem already, it was definitely possible (and done).

--------------------

Practice Problem: Show that the sum of the digits of a number is congruent to itself modulo nine.