IMO problem

henryzz · 2020-04-12, 19:47

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.

retina · 2020-04-12, 19:51

Quote:

Originally Posted by henryzz

Find the sum of the digits of the sum of the digits of the sum of the digits of 4444^4444.

I assume this is expected to be digits in base 10?

In base 4444 then answer is 1

R.D. Silverman · 2020-04-12, 20:25

Quote:

Originally Posted by henryzz

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.

Hint: 9

retina · 2020-04-12, 20:45

Oh cool. 55555^55555 gives the same result.

axn · 2020-04-13, 02:33

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.

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, now we can apply Bob's hint and compute the answer, knowing that is going to be a single digit answer.

4444 % 9 = 7
4444 % eulerphi(9) = 4

LaurV · 2020-04-13, 05:15

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

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

retina · 2020-04-13, 05:42

Quote:

Originally Posted by LaurV

Yes, it can be 10 too!

I don't think so. My analysis showed that 10 can't be reached. Did I make a mistake?

LaurV · 2020-04-13, 06:03

Yes you did

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

R.D. Silverman · 2020-04-13, 11:42

Quote:

Originally Posted by LaurV

Yes you did

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

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

axn · 2020-04-13, 13:11

Quote:

Originally Posted by R.D. Silverman

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

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

LaurV · 2020-04-14, 05:28

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

Interesting, if the puzzle would ask for 4444^4443, most of the "solvers" here would have failed the answer

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 second sum. You can try something like the next line, to make sure. Then you see how you prove this formally...

Code:

gp> for(i=1,4444,print(i": ",a=vecsum(digits(4444^i)),", ",b=vecsum(digits(a)),", ",c=vecsum(digits(b))))

2020-04-12, 19:47	#1
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 2³×3×5×7² Posts	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.

2020-04-13, 02:33	#5
axn Jun 2003 5,051 Posts	4444 has about 3.5 digits. So 4444^4444 has about 3.54444 = 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. 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, now we can apply Bob's hint and compute the answer, knowing that is going to be a single digit answer. 4444 % 9 = 7 4444 % eulerphi(9) = 4 Last fiddled with by Dr Sardonicus on 2020-04-13 at 13:39 Reason: Spoilerized at user request*

2020-04-13, 05:15	#6
LaurV Romulan Interpreter Jun 2011 Thailand 10010110001011₂ Posts	Hint: It can only be 1, 4, 7, or 10 Yes, it can be 10 too! It is not necessary to be a single digit. grrr.. axn's post should be in spoilers too! Last fiddled with by LaurV on 2020-04-13 at 05:20

2020-04-13, 06:03	#8
LaurV Romulan Interpreter Jun 2011 Thailand 7·1,373 Posts	Yes you did . To get to 1 you would need one more sum. Try for example n=18 (the smallest such). Last fiddled with by LaurV on 2020-04-13 at 06:06

2020-04-14, 05:28	#11
LaurV Romulan Interpreter Jun 2011 Thailand 258B₁₆ Posts	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 Interesting, if the puzzle would ask for 4444^4443, most of the "solvers" here would have failed the answer 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 second sum. You can try something like the next line, to make sure. Then you see how you prove this formally... Code: gp> for(i=1,4444,print(i": ",a=vecsum(digits(4444^i)),", ",b=vecsum(digits(a)),", ",c=vecsum(digits(b)))) Last fiddled with by LaurV on 2020-04-14 at 05:43

2020-04-12, 20:45	#4
retina Undefined "The unspeakable one" Jun 2006 My evil lair 1100000110100₂ Posts	Oh cool. 55555^55555 gives the same result.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
A new problem similar to the Collatz problem	dabler	Miscellaneous Math	1	2018-07-28 14:03
problem I have	science_man_88	Miscellaneous Math	2	2010-10-10 16:36
PSU problem?	ian209	Hardware	4	2006-02-18 19:52
51 problem	Neves	Miscellaneous Math	5	2004-02-10 22:59
51 problem	Neves	Puzzles	15	2004-02-05 23:11