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).
Problem
Source: IMO ShortList 1990, Problem 8 (HUN 1)
Tags: number theory, Digits, sum of digits, Calculate, decimal representation, IMO Shortlist
28.08.2008 20:03
Since 21990 < 8700 < 10700, we have f1(21990) < (9·700)2 < 4·107. We then have f2(21990) < (3+9·7)2 < 4900 and finally f3(21990) < (3+9·3)2 = 302. It is easily shown that fk(n) ≡ fk−1(n)2 (mod 9). Since 26 ≡ 1 (mod 9), we have 21990 ≡ 24 ≡ 7 (all congruences in this problem will be mod 9). It follows that f1(21990) ≡ 72 ≡ 4 and f2(21990) ≡ 42 ≡ 7. Indeed, it follows that f2k(21990) ≡ 7 and f2k+1(21990) ≡ 4 for all integer k > 0. Thus f3(21990) = r2 where r < 30 is an integer and r ≡ f2(21990) ≡ 7. It follows that r ∈ {7, 16, 25} and hence f3(21990) ∈ {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.
29.08.2008 15:31
ramakrishna wrote: Since 21990 < 8700 ⋯ Umm...
02.10.2019 17:45
It is well known that, in base 10, the sum of a number's digits is congruent to number itself, modulo 9. So we are motivated to work modulo 9. First, we use the fact that 26≡1 (mod 9) to deduce that 21990≡7 (mod 9). Next, working in modulo 9 (including the arguments of the function), we see that f1(7)≡4 and f1(4)≡7. Since 1991 is odd, we deduce that f1991(21990)≡4 (mod 9) The jist from here is that the numbers f1(21990), f2(21990), f3(21990)… etc. are all perfect squares, get small really quickly, and stay small. So we only have to search small perfect squares which are 4 or 7 modulo 9. We find that 132 and 162 are the two attractors, and so we choose the one which is 4 modulo 9. Hence, f1991(21990)=256.
Attachments:

20.07.2024 08:11
aight first note that 2^{1990}\equiv 7\pmod{9} since \log_{10}{2}<\frac13 we know f_1(2^{1990})\le (700\cdot9)^2\le 4\cdot 10^7 and is 4\pmod9 note that 3+9\cdot 7=66 but digit sum is 4\pmod9 so f_2(2^{1990})\le 58^2\le 3600 and is 7\pmod9 2+9+9+9=29 but digit sum is 7\pmod{9} so f_3(2^{1990})\le 25^2=625 and is 4\pmod{9} 5+9+9=23 but digit sum is 4\pmod{9} so f_4(2^{1990})\le 22^2=484 and is 7\pmod9 3+9+9=21 but digit sum is 7\pmod{9} so f_5(2^{1990})\le 16^2=256 and is 4\pmod9 1+9+9=19 but digit sum is 4\pmod{9} so f_6(2^{1990})\le 13^2=169 and is 7\pmod{9} the digit sum is either 7 or 16 which go to 49 and 256 respectively which both go to 169 f_8(2^{1990})=f_{10}(2^{1990})=\dots=f_{1990}(2^{1990})=169 the answer is \boxed{256}
30.07.2024 08:51
Note that 2^{1990}=1024^{199} < 10000^{199} = 10^{796}< 10^{1434}. As a result, 2^{1990} has 1434 digits or less. Note that f(2^{1990}) \le f(9999....9999) = (9*1434)^2 = 166564836, where the 9 is repeated 1434 times. Note that f(166564836) \le f(999999999) = (9*9)^2=6561 Note that f(6561) \le f(9999) = (9*4)^2=1296 Note that f(1296) \le f(999) = (9*3)^2=729. Note that anything less than 1296 also satisfies this property, since the maximum possible four digit sum would be 1+1+9+9=20 < f(999). Note that f(729) \le f(699) = (6+9+9)^2=576 Note that f(576) \le f(499) = (4+9+9)^2=484 Note that f(484) \le f(399)=441 As a result, f_{1991}(2^{1990}) \le 441 and f_{1990}(2^{1990}) \le 441. Note that k^2 \equiv f_1(k) \pmod 9 due to divisibility rules Also, get that 2^{1990} \equiv 2^4 \equiv 7 \pmod 9. As a result, get that f_1(k) \equiv 49 \equiv 4 \pmod 9, f_2(k) \equiv 16 \equiv 7 \pmod 9, and this repeats, so get that f_{1991}(2^{1990}) \equiv 4 \pmod 9 Also, get that f_{1991}(2^{1990}) is a perfect square. As a result, get that it can equal to 4,49,121,256,400. So get that the sum of digits of f_{1990}(2^{1990}) can equal to 2,7,11,16,20 Note that f_{1990}(2^{1990}) is a square. Note that the values of squares mod 9 are 0,1,4,7. As a result, the sum of the digits f_{1990}(2^{1990}) cannot equal 2,11, or 20. This only leaves 7 and 16. Note that since f_{1990}(2^{1990}) is a square, is less than or equal to 441, and is 7 mod 9. As a result, the possible values of this include 16, 25, 169, 196. So get that the sum of digits of f_{1989}(2^{1990}) can equal to 4,5,13,14. But since f_{1989}(2^{1990}) \equiv 4 \pmod 9, this only leaves 4 and 13. Repeat the same logic to get that the sum of the digits of f_{1988}(2^{1990}) can be 7 and 16. If the sum is 7, then this can equal 16 or 25. Then, f_{1989}(2^{1990})=256, since 25^2=625 is too big. This results in f_{1990}(2^{1990})=169 and f_{1991}(2^{1990})=256 If the sum is 16, then this can equal 169 or 196. Then, f_{1989}(2^{1990})=256. This also results in f_{1990}(2^{1990})=169 and f_{1991}(2^{1990})=256. As a result, f_{1991}(2^{1990})=\boxed{\boxed{\boxed{\boxed{256}}}}
15.08.2024 22:41
Rename f_1 to f. Note that f(2^{1990})\le (9\cdot 1990)^2<4\cdot 10^8. Then f of something less than 4\cdot 10^8 is at most (3+9+9+9+9+9+9+9+9)^2=75^2=5625. Then f of something \le 5625 is at most (4+9+9+9)^2=31^2=961. Then f of somthing \le 961 is at most (8+9+9)^2=26^2=676. Then f of something \le 676 is at most (5+9+9)^2=23^2=529. Then f of something \le 529 is at most (4+9+9)^2=22^2=484. Then f of something \le 484 is at most (3+9+9)^2=21^2=441. That is, the sequence after a few terms will be \le 441. Now we will consider what each square at most 441 maps to. 1\to 1 4\to 16 9\to 81 16\to 49 25\to 49 36\to 81 49\to 169 64\to 100 81\to 81 100\to 1 121\to 16 144\to 81 169\to 256 196\to 256 225\to 81 256\to 169 289\to 361 324\to 81 361\to 100 400\to 16 441\to 81 So immediately we can see that stuff don't last very long. In particular, the only things that get mapped to are 1,16,49,81,100,169,256,361. 1\to 1 16\to 49 49\to 169 81\to 81 100\to 1 169\to 256 256\to 169 361\to 100 Now we see that 361 is no longer mapped to. After removing that, 100 is no longer mapped to. Also, 16 is no longer mapped to. After removing that, 49 is no longer mapped to. 1\to 1 81\to 81 169\to 256 256\to 169 Ok. Now we will look back at our original function f. Note that 2^{1990} is 7 mod 9. Note that f maps something 7 mod 9 to something 7^2\equiv 4\pmod 9, and maps something 4 mod 9 to something 4^2\equiv 7\pmod 9. Therefore, after applying f 1991 times, the result will be something 4 mod 9. The only one of these that is 4 mod 9 is \boxed{256}. So that's the answer. \blacksquare