For a given positive integer $ k$ denote the square of the sum of its digits by $ f_1(k)$ and let $ f_{n+1}(k) = f_1(f_n(k)).$ Determine the value of $ f_{1991}(2^{1990}).$
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 $ \cdots$ 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 $2^6 \equiv 1 \text{ (mod } 9)$ to deduce that $2^{1990} \equiv 7 \text{ (mod } 9)$. Next, working in modulo $9$ (including the arguments of the function), we see that $f_1(7) \equiv 4$ and $f_1(4) \equiv 7$. Since $1991$ is odd, we deduce that $f_{1991}(2^{1990}) \equiv 4 \text{ (mod } 9)$ The jist from here is that the numbers $f_1(2^{1990})$, $f_2(2^{1990})$, $f_3(2^{1990}) \dots$ 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 $13^2$ and $16^2$ are the two attractors, and so we choose the one which is $4$ modulo $9$. Hence, $f_{1991}(2^{1990}) = 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$