Hints for Problem 24

Here is an outline of what you should do:

We want to find Q(Q(Q(4444^{4444}))). The naive way (which turns out utterly unfeasible) would be: calculate 4444^{4444}, add up all its digits, write down the result, which is Q(4444^{4444}), add up all the digits of this result, obtain Q(Q(4444^{4444})), and then do it again.

This is utterly unfeasible since 4444^{4444} is so huge that it doesn’t fit onto your pocket calculator. Get a rough idea how many digits 4444^{4444} has. (Fancy how many pages it would need to write them all down with 80 digits per line and 60 lines per page!)

You want an upper bound for the number of digits of 4444^{4444}: “at most that many”. And you want to conclude: since 4444^{4444} has at most ***** digits, Q(4444^{4444}) (which is the sum of its digits) can be at most *****. Since it is at most *****, it has at most **** digits and therefore the Q(·) of this number can be at most ****. Continue that way until you get a result of the form Q(Q(Q(4444^{4444}))) ≤ some small number. That’s part 1 of your job

Next you should remember that for any positive integer x, it holds Q(x) ≡ x (mod 9). Maybe I need to remind some of you that this is what we discussed in class. For instance, for the number 368294585127, we have Q(368294585127) = 3 + 6 + 8 + 2 + 9 + 4 + 5 + 8 + 5 + 1 + 2 + 7 = 60, and 368294585127 ≡ 60 (mod 9). This result holds in particular for x = 4444^{4444}, whence Q(4444^{4444}) ≡ 4444^{4444} (mod 9). It also holds for x = Q(4444^{4444}), whence Q(Q(4444^{4444})) ≡ Q(4444^{4444}) (mod 9). And you do the next step.

This means: If you can find in which congruence class ([0], [1], [2], [3], [4], [5], [6], [7], [8]) mod 9 the number 4444^{4444} is, you know that Q(Q(Q(4444^{4444}))) is in the same congrunece class.

The punchline now is: Even though 4444^{4444} is prohibitively huge, you can still figure out its congruence class mod 9 quite easily. To this end I may need to remind you that we showed in class: If a_{1} ≡ a_{2} (mod 9) and b_{1} ≡ b_{2} (mod 9), then a_{1}b_{1} ≡ a_{2}b_{2} (mod 9). This means in particular:

Since 4444 ≡? (mod 9) (you figure out the question mark), we have 4444 · 4444 ≡?·? (mod 9), and continuing 4444 · 4444 · 4444 ≡?·?·? (mod 9) etc. Inductively, if a_{1} ≡ a_{2} (mod 9), then a_{1}^{n} ≡ a_{2}^{n} (mod 9). for all natural numbers n.

Now go ahead finding the congruence class (mod 9) of 4444^{4444}; in your step by step calculation, you may replace numbers that become large by smaller numbers in the same congruence class. That gives the second piece of information.

Take the two pieces of information together and answer the question from the problem.