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?

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Aang Jul 12 '12 at 6:05
  • 1
    $\begingroup$ Sorry sir Avatar. I edited it. $\endgroup$ – Hyperbola Jul 12 '12 at 6:10
  • 9
    $\begingroup$ @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. $\endgroup$ – ShreevatsaR Jul 12 '12 at 6:11
  • $\begingroup$ I understand what you are saying(my mistake), i am editing it. $\endgroup$ – Aang Jul 12 '12 at 6:28
  • $\begingroup$ It is worth mentioning that this problem appears in Problems for Mathematicians Young and Old by Halmos. $\endgroup$ – JMoravitz Mar 4 '16 at 6:19
14
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ No problem. I think that question was an IMO question about 35-40 years ago. $\endgroup$ – Old John Jul 12 '12 at 5:53
  • $\begingroup$ @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$. $\endgroup$ – Aang Jul 12 '12 at 5:58
  • $\begingroup$ @OldJohn: sorry, i understood the problem wrong, you are right. $\endgroup$ – Aang Jul 12 '12 at 6:00
  • 2
    $\begingroup$ 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. $\endgroup$ – Old John Jul 12 '12 at 6:00
  • 7
    $\begingroup$ 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. $\endgroup$ – celtschk Jul 12 '12 at 7:32
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.