[PetteriLem]

Let N be the sum of 4444 to power 4444 digits and M the sum of N's digits. What is the sum of M's digits?

[Trumpace]

This is an old International Math Olympiad problem, and if I recall correctly, the answer is ..

Spoiler

seven

..

[G_R__E_G]

My first instinct is the smart ass reply of "L". Of course, my first instinct is most often the smart assed response.

That said, upon further thought I'm going with ...

Spoiler

19

.

[Trinidad]

The sum is 1.

Does it matter that I didn't use decimal numbers but that I used the number 4444 as the base of my numerical system?



Rik

[TimG]

I'm going with ...

Spoiler

four

...

[Echognome]

PetteriLem, on Sep 12 2008, 09:25 AM, said:

Let N be the sum of 4444 to power 4444 digits and M the sum of N's digits. What is the sum of M's digits?

I'm a bit confused by the question.

So we have N = sum of digits of 4444^4444
and M = sum of digits of N?

I know these aren't the correct answers, but just so I understand the question, suppose that:

4444^4444 = 498461316168181646

So then N = 4+9+8+4+6+1+3+1+6+1+6+8+1+8+1+6+4+6 = 83
and M = 8+3 = 11.

Is that the way we are supposed to go about calculating it, assuming we could find the right number for 4444^4444?

[TimG]

I was confused by the wording, too, but interpreted it the same way as you, so I guess it wasn't as unclear as we thought.

[naresh301]

I'm pretty sure I've seen this or a very similar math olympiad problem. Gnome and TimG's interpretations are correct (if M=11, the answer would be 2).

I have the same answer as Trumpace.

[EricK]

I agree with the answers given already.

Hidden working:

Spoiler

Step 1. 4444mod9=7; 7^6mod9=1; 4444mod 6=4; 7^4mod9=7. Hence 4444^4444 mod9=7

Step 2. Log10(4444)<4, hence log10(4444^4444)<17776. Hence 4444^4444 has at most 17776 digits. Hence the sum of these digits, N < 9*17776 = 159984.
Hence the sum of digits of N = M < 1+4+9+9+9+9=41
Hence the sum of the digits of M < 3+9= 12

The sum of the digits of a number is equalt to the number modulo 9. Hence from step 1 and step 2, the sum of the digits of M must be 7 as this is the only number less than 12 which is equal to 7 modulo 9

[gwnn]

Eric, I think you're wrong about your 41, it should be 45. Of course that doesn't make your final answer wrong. Very nice solution btw.

[TimG]

EricK, on Sep 13 2008, 03:44 AM, said:

The sum of the digits of a number is equal to the number modulo 9.

That can't be true, can it? Doesn't it imply that the sum of the digits of any multiple of 9 is 0?

Even if I am mistaken and 9 mod 9 = 9, what of 19? 1 + 9 = 10; 19 mod 9 = 1.

Maybe the sum of the digits of the sum of the digits eventually equals the number mod 9 when carried out enough times so that the sum is less than 10. i.e the sum of the digits for 19 is 10, the sum of those digits is 1 which equals 19 mod 9.

But, the problem stipulated only two steps.

[EricK]

gwnn, on Sep 13 2008, 10:00 AM, said:

Eric, I think you're wrong about your 41, it should be 45. Of course that doesn't make your final answer wrong. Very nice solution btw.

Yes, you are right. It should be 45.

[EricK]

TimG, on Sep 13 2008, 11:47 AM, said:

EricK, on Sep 13 2008, 03:44 AM, said:

The sum of the digits of a number is equal to the number modulo 9.

That can't be true, can it? Doesn't it imply that the sum of the digits of any multiple of 9 is 0?

Even if I am mistaken and 9 mod 9 = 9, what of 19? 1 + 9 = 10; 19 mod 9 = 1.

Maybe the sum of the digits of the sum of the digits eventually equals the number mod 9 when carried out enough times so that the sum is less than 10. i.e the sum of the digits for 19 is 10, the sum of those digits is 1 which equals 19 mod 9.

But, the problem stipulated only two steps.

I meant that a number and the sum of its digits are congruent to each other modulo 9 (i.e. leave the same remainder upon dividing by 9) or in more general terms:

Let N be a positive integer and let D be the sum of the digits of the representation of N in base b. Then N≡D(mod b-1)

This means, when applied to the problem in the OP, that 4444^4444, the sum of the digits of 4444^4444, the sum of the digits of that number, the sum of the digits of that number and so on, all leave the same remainder upon dividing by 9. Which, as can be easily shown, is 7. The second half of the proof showed that 7 itself was the only option for the sum of the digits of M because the next option, 16 was already too high.

[TimG]

TimG, on Sep 12 2008, 01:03 PM, said:

I'm going with ...

Spoiler

four

...

I was mistakenly trying to solve the problem for 4^4444. Probably still wrong...