IMO 1990 SL 8

Origin: HUN

Problem

For a given positive integer k denote the square of the sum of its digits by f1(k) and let fn+1(k) = f1(fn(k)). Determine the value of f1991(21990).

Solution

Since 21990 < 8700 < 10700, we have f1(21990) < (9\cdot700)2 < 4\cdot107. We then have f2(21990) < (3+9\cdot7)2 < 4900 and finally f3(21990) < (3+9\cdot3)2 = 302. It is easily shown that fk(n) \equivfk−1(n)2 (mod 9). Since 26 \equiv1 (mod 9), we have 21990 \equiv24 \equiv7 (all congruences in this problem will be mod 9). It follows that f1(21990) \equiv72 \equiv4 and f2(21990) \equiv42 \equiv7. Indeed, it follows that f2k(21990) \equiv7 and f2k+1(21990) \equiv4 for all integer k > 0. Thus f3(21990) = r2 where r < 30 is an integer and r \equivf2(21990) \equiv7. It follows that r \in{7, 16, 25} and hence f3(21990) \in{49, 256, 625}. It follows that f4(21990) = 169, f5(21990) = 256, and inductively f2k(21990) = 169 and f2k+1(21990) = 256 for all integer k > 1. Hence f1991(21990) = 256.