21

Let $A = 4444^{4444}$;

Then sum of digits of $A = B$;
Then sum of digits of $B = C$;
Then sum of digits of $C = D$;

Find $D$.

What should be the approach here?

Aang
  • 14,672
Hyperbola
  • 2,425

2 Answers2

18

The approach is to use the fact that $4444 \equiv 7 \pmod 9,$ so that $4444^3 \equiv 1 \pmod 9,$ and then get $4444^{4444} \equiv 7 \pmod 9$.

Then use the fact that for any integer $N$, the sum of the digits of N is equivalent to $N \pmod 9$.

Finally use logs to base 10 to get a limit on the size of $A$, hence $B$ etc.

The answer is 7, if I remember correctly.

Old John
  • 19,569
  • 3
  • 59
  • 113
  • 4
    No problem. I think that question was an IMO question about 35-40 years ago. – Old John Jul 12 '12 at 05:53
  • 1
    @OldJohn: $4444^{4444}\pmod 9$ doesn't give the sum of the digits of $4444^{4444}$ but the repeated sum, for example $4^4\pmod 9=256\equiv 4\pmod 9$ but digit sum of $256=13$. – Aang Jul 12 '12 at 05:58
  • @OldJohn: sorry, i understood the problem wrong, you are right. – Aang Jul 12 '12 at 06:00
  • 2
    Yes, the fact that $4444^{4444}\equiv 7 \pmod 9$ only narrows the final answer down to the series $7, 16, 23, \dots$. You then have to use the log argument to narrow it down to 7. I recall doing something like finding the number of digits of $A$ using logs to base 10, then get a limit on $B$ by assuming they are mostly 9s, etc. – Old John Jul 12 '12 at 06:00
  • 8
    There's the fact that $4444^{4444}$ has at most $4\cdot4444=17776$ digits (actually it has less). The sum of digits can therefore not be larger than $17776\cdot9=159984$ which has only $6$ digits, which means the sum of sum of digits cannot be larger than $6\cdot9=54$. Since the largest sum of digits of a number $\le54$ is $13$ (the sum of digits of $49$), the sum of sum of sum of digits cannot be larger than $13$, and since $16$ is already larger, $7$ remains as the only possible (and thus the correct) solution. – celtschk Jul 12 '12 at 07:32
  • Also, through putting $x=4444^{4444}, 4444 \equiv -2$ (mod $9$), so $x = (-2)^{4444}$ (mod $9$). But $(-2)^3 \equiv 1$ (mod $9$), and $4444 \equiv 1$ (mod $3$), so $x \equiv -2 \equiv 7$ (mod $9$). –  Sep 23 '16 at 13:30
5

It's well-known that, because $10 \equiv 1 \bmod 9$, and therefore $10^k = 1 \bmod 9$ for all $k>0$, we have that the sum of digits of $n$, $S(n) \equiv n \bmod 9$.

So what is $4444^{4444} \bmod 9$? The above equivalence gives us that $4444 \equiv 7 \bmod 9$.

Now we need the order of $7$ modulo $9$, the smallest $s$ such that $7^s \equiv 1 \bmod 9$. This is easy to find by examination: $7^2 \equiv 4 \bmod 9$ and so $7^3 \equiv 28 \equiv 1 \bmod 9$.

So $4444^{4444} \equiv 7^{4444} \equiv 7 \cdot (7^3)^{1481} \equiv 7 \ \bmod 9$, and the same equivalence is true for $B,C$ and $D$.

Now roughly how big is $A$? Since $\log_{10}4444 \approx 3.64777$, we know that $\log_{10}A \approx 16210.7$, that is $A$ has $16211$ digits. This gives us that $B \le 16211\times 9 = 145899$. So if $B>100000$, the first two digits sum to no more than $5$, which means that $C \le 45$ (that maximum being when $B=99999$).

Finally we can use our knowledge that $C \equiv 7 \bmod 9$ and observe that $C$ must be one of the values $\{7,16,25,34,43\}$ and thus that $S(C) = \fbox{D = 7}$.

Additional thoughts:

We get exactly the same answer, $D=7$, for $A=55555^{55555}$ . Impressively, a slight variation on the same process also works to get $D=9$ for the case $A=999999999^{999999999}$ (nine nines).

Joffan
  • 39,627