IMO problem
 

Today I came across the solution to a problem from the International Mathematical Olympiad 1975 which I quite liked. I thought I would share the problem and see if anyone here can come up with the solution.
The problem:
Find the sum of the digits of the sum of the digits of the sum of the digits of 4444^4444.
This can be done without a calculator.

[QUOTE=henryzz;542458]Find the sum of the digits of the sum of the digits of the sum of the digits of 4444^4444.[/QUOTE]I assume this is expected to be digits in base 10?

[size=1]In base 4444 then answer is 1[/size]

[QUOTE=henryzz;542458]Today I came across the solution to a problem from the International Mathematical Olympiad 1975 which I quite liked. I thought I would share the problem and see if anyone here can come up with the solution.
The problem:
Find the sum of the digits of the sum of the digits of the sum of the digits of 4444^4444.
This can be done without a calculator.[/QUOTE]

Hint: 9

Oh cool. 55555^55555 gives the same result.

[spoiler]4444 has about 3.5 digits. So 4444^4444 has about 3.5*4444 = 15554 digits in it. The average digit is 4.5, so the s-o-d of 4444^4444 is appr. 69993. (The exact answer is 72601). But worst case is all 9's, so it could be as high as 139986.[/spoiler]

[spoiler]Out of this, worst case is 99999, which yields a sum-of-digit of 45. So by second sum of digit we're safely in two digit territory. With sizes suitably constrained[/spoiler], now we can apply Bob's hint and compute the answer, [spoiler]knowing that is going to be a single digit answer.[/spoiler]

[spoiler]4444 % 9 = 7
4444 % eulerphi(9) = 4[/spoiler]

Hint: It can only be [SPOILER]1, 4, 7, or 10[/SPOILER] Yes, it can be [SPOILER]10[/SPOILER] too! It is not necessary to be [SPOILER]a single digit[/SPOILER].


grrr.. axn's post should be in spoilers too! :razz:

[QUOTE=LaurV;542501]Yes, it can be [SPOILER]10[/SPOILER] too![/QUOTE][spoiler]I don't think so. My analysis showed that 10 can't be reached. Did I make a mistake?[/spoiler]

Yes you did :razz:. To get to 1 you would need one more sum. Try for example n=18 (the smallest such).

[QUOTE=LaurV;542505]Yes you did :razz:. To get to 1 you would need one more sum. Try for example n=18 (the smallest such).[/QUOTE]

You are wrong. Let lg mean log base 10. Then lglglg (4444^4444) < 1.

[QUOTE=R.D. Silverman;542514]You are wrong. Let lg mean log base 10. Then lglglg (4444^4444) < 1.[/QUOTE]

But not lg( 9*lg(9*lg(4444^4444)) )

Well, to cut any suspicions: (sorry for spoiling it, but it was spoiled enough, who wanted to solve it, solved it already, as some already gave out the answer, and axn already gave the first exact sum, which stayed without spoiler tags. Anyhow, if you didn't solve it yet, and want to solve it by yourself, then don't scroll down the code section below).
[CODE]
gp > for(i=1,4444,print(i": "vecsum(digits(vecsum(digits(vecsum(digits(4444^i))))))))
1: 7
2: 4
3: 1
4: 7
5: 4
6: 1
7: 7
8: 4
9: 1
10: 7
11: 4
12: 1
13: 7
14: 4
15: 1
16: 7
17: 4
18: 10
19: 7
20: 4
21: 1
22: 7
23: 4
24: 1
25: 7
26: 4
27: 1
28: 7
29: 4
30: 1
31: 7
32: 4
33: 1
34: 7
35: 4
36: 10
37: 7
38: 4
39: 1
40: 7
41: 4
42: 10
43: 7
44: 4
45: 1
46: 7
47: 4
48: 10
49: 7
50: 4
.....<snip>.....
4400: 4
4401: 10
4402: 7
4403: 4
4404: 10
4405: 7
4406: 4
4407: 10
4408: 7
4409: 4
4410: 10
4411: 7
4412: 4
4413: 10
4414: 7
4415: 4
4416: 10
4417: 7
4418: 4
4419: 10
4420: 7
4421: 4
4422: 10
4423: 7
4424: 4
4425: 10
4426: 7
4427: 4
4428: 10
4429: 7
4430: 4
4431: 10
4432: 7
4433: 4
4434: 10
4435: 7
4436: 4
4437: 10
4438: 7
4439: 4
4440: 10
4441: 7
4442: 4
4443: 10
4444: 7

[/CODE]Interesting, if the puzzle would ask for 4444^4443, most of the "solvers" here would have failed the answer :razz:

Getting 1 or 10 as final answer hasn't much to do with that logarithm, but with getting 19 as the second sum. Even if you max would only be 25, yet 2+5 is 7, or 2+1 is 3, but 1+9 is 10, even if 19 is smaller than 21 or 25. This is similar with doing x^2 (mod 2^n-1) which we do at LL test, by adding the first n bits to the last n bits, sometimes you do not get zero, in fact, you never get zero, but you may get 1111...111, and you need one more mod cut. You can only get 1 if you get 10 as the [U]second[/U] sum. You can try something like the next line, to make sure. Then you see how you prove this formally... :razz:
[CODE]gp> for(i=1,4444,print(i": ",a=vecsum(digits(4444^i)),", ",b=vecsum(digits(a)),", ",c=vecsum(digits(b))))[/CODE]