16
$\begingroup$

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?

  • 0
    what you are asking is simply called the repeated sum of digits(no need to write it as sum of sum of sum of digits,it's confusing).2012-07-12
  • 1
    Sorry sir Avatar. I edited it.2012-07-12
  • 9
    @avatar: No, "sum of sum of sum of digits" is different, and presumably what the OP wants, since he says "D" specifically, not "repeat the process...". At any rate, "sum of sum of sum of digits" is a more interesting problem (involves estimating the size, etc.) than repeated sum.2012-07-12
  • 0
    I understand what you are saying(my mistake), i am editing it.2012-07-12
  • 0
    It is worth mentioning that this problem appears in [Problems for Mathematicians Young and Old](http://www.amazon.com/Problems-Mathematicians-Dolciani-Mathematical-Expositions/dp/0883853205) by Halmos.2016-03-04

3 Answers 3

14

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.

  • 2
    No problem. I think that question was an IMO question about 35-40 years ago.2012-07-12
  • 0
    @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$.2012-07-12
  • 0
    @OldJohn: sorry, i understood the problem wrong, you are right.2012-07-12
  • 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.2012-07-12
  • 7
    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.2012-07-12
  • 0
    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$).2016-09-23
3

The link below includes the whole analysis; you might want to see it http://www.artofproblemsolving.com/Wiki/index.php/1975_IMO_Problems/Problem_4

1

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).