fffffour
The sum of the digits of 4444^4444 is A. The sum of the digits of A is B. The sum of the digits of B is C. What is the value of C?
For info on modular arithmetic try:
http://www.cut-the-knot.org/blue/Modulo.shtml
For info on modular arithmetic try:
http://www.cut-the-knot.org/blue/Modulo.shtml
Labels: mathschallenge
posted by Chris at
7:01 PM
12 Comments:
5
Close. How did you do it?
I thought 5 as well.
Taking the sum of the digits of 4444^4444 as it stands, i.e. as an expression rather than evaluating it, then this 8 * 4 = 32 (A). The sum of the digits of 32 is 5 (B). The sum of the digits of 5 is again 5 (C).
The length of A is 16211
Summing the digits of A is : 72601
The length of B is 5
The sum of the digits of B is C which is 16
Ragknot. I thought I was going to defeat your computer this time. I assume that you've got some fancy large number maths libraries at your disposal. But you have a human error in your first statement. You'll get the whole thing right almost immediately (just after you kick yourself) when you spot it.
Wiz. Try 4^4 = 256. 4+4=8 and 2+5+6 = 13 => 1+3 = 4, so that idea doesn't work. At least I know where the first 5 came from.
I wasn't expecting any to actually find the value of 4444^444, A or B.
I can't tell from the responses who remembers the trick way of testing if a number is divisible by 9 - and what if it isn't divisible by 9. That clue will get you some, but not all, of the way. After that you will need to try another tactic. The other tactic will require a leap of faith involving only a few simple steps before you can simplify the problem enormously. Ragknots's info is correct (except that he's out of step ^^).
The 4444 to the power of 4444 has 16211 digits
The sum of the 16211 digits is 72601 so A= 72601
Summing the digits of A is 16 which is B.
The sum of the digits of B is C which is 7
Ragknot has provided the answer using his super-computer.
The only things that I used a calculator for was to determine that 4444^4444 is a 16211 digit number. I also used a calculator for the next step, but I could easily have done that by hand.
You'll find it helpful to only try to find the maximum possible values of A, B and C. You'll need Cmax at the end. You'll need to use modular arithmetic extensively for the rest of the problem.
I don't have a super computer.
But a while back I found some old basic programs that computed BIG numbers. I put them in a visual basic module with some modifications. The programs I gathered were all FREE. So I can share them if you email me at ragknot@gmail.com
To find the big number in this, I just used a function ,,,
Ffffffour = strpow(4444,4444)
Ragknot. Sorry, I was being flippant about the super computer. I
should have known that you would have a large number library.
The value of C is 7. From now, all variables are non-negative
integers. I'll be concise to minimise space. I added some notes
about modular/modulo arithmetic at the end..
Let N = 4444^4444. Then log N = 4444*log4444 => N has 16211 digits.
=> max possible sum of the digits of N = Amax = 9*16211 = 145899.
The first two digits can sum to 9 at most. So the max possible
value of B = Bmax = 5*9 = 45. And so the max value of the sum of
the digits of B = Cmax = 12. We'll need that result later.
Binomial theorem => (a+b)^n = a^n + integral multiple of b.
=> (a+b)^n = a^n (mod b). Now I'll show that the sum of the digits
of N = N (mod 9). First, 10^n = (9+1)^n = 1^n = 1 (mod 9)
Let N = a + b*10 + c*10^2 + d*10^3 + ... (defn of decimal system)
Then N = a + b + c + d + ... (mod 9) => if the remainder of a
number after division by 9 is r, then the remainder of the sum of
the digits after dividing by 9 is r also. This can be applied
recursively. So C = B = A = N (mod 9).
If x = y (mod m) then x^n = y^n (mod m). [See note 4].
In our case 4444 = 7 (mod 9), so 4444^4444 = 7^4444 (mod 9).
Now, 7^0 = 1 (mod 9), 7^1 = 7 (mod 9), 7^2 = 49 = 4 (mod 9),
7^3 = 28 = 1 (mod 9) and the cycle then repeats. So the only bit
of the power that matters is given by 4444 = 1 (mod 3).
Altogether we have 4444^4444 = 7^1 = 7 (mod 9). This says that
C could be 7, 16, 24, 33 ... (adding 9 at each step). Earlier we
saw that Cmax = 12, so we conclude that C = 7.
Basic modular arithmetic. (Every variable is an integer).
1: If x = a*m + r and y = b*m + r then x = y = r (mod m).
Let x = p (mod m) and y = q (mod m), then
2: x + y = p + q (mod m)
3: x * y = p * q (mod m)
4: If x = y (mod m), then x^n = y^n (mod m)
Proof: using 3, x*x = y*y (mod m). Repeat x*x*x = y*y*y (mod m)
just keep going.
Isn't the trick way to tell if a number is divisible by 9 is that the sum of its parts must also be divisible by 9?
Anonymous, that was proven in the fourth paragraph of the solution.
Post a Comment
Links to this post:
Create a Link
<< Home