Impossible math question

[kyro]

This was in a math puzzle book I own. The explanation made no sense to me. I'm curious if anyone can figure this one out. I'll post the answer to it sometime tomorrow or the day after. Good luck.


SOD = sum of digits. Therefore, SOD(356) = 3 + 5 + 6 = 14.

What is SOD(SOD(SOD(4444^4444)))?

[lightw1thoutheat]

heres my work
let x=4444^4444
let A= s.o.d (x)
let B= s.o.d (A)
let C= s.o.d (B)
first, lets re-examine mod 9, because a number in decimal expansion is congruent to the sum of its digits mod 9. This is because each power of 10 is congruent to 1 mod 9.

so 4444=-2 mod 9
also see that (-2)^3=1 mod 9
(Note: = will mean congruent for a while)

so x=(-2)^4440 * (-2)^4 mod 9
and 3|4440, so
x=(-2)^3 * (-2)^4 mod 9
x=1 * (-2)^4 mod 9= -2 mod 9

so a= -2 mod 9

1000^4444< 4444^4444< 10000^4444
digits: 4444*3+1 < ? < 4444*4+1
so 4444^4444 has less than 18,000 digits
so A< 18000*9=16200 (6 digits)
so B< 9*6=54

the number <= 54 with the largest sum of digits is 49.

so s.o.d. (b) <4+9=13

we know b=-2 mod 9 and s.o.d (b)=-2 mod 9

so, -2= y mod 9 0=< y =< 13

so y=7

the answer is 7

[lightw1thoutheat]

kinda neat, im sure theres a more elegant way to do it, but i in fact this exact problem challenged to me this week. (havent had time to discuss this exact solution with my team leader yet, although im sure its right)

i am lame in the fact that im in a problem solving team at school, but ive got a bunch more of these problems if anyone's interested.
-light

[fatdave]

Isn't "SOD(SOD(SOD(4444^4444)))" redundant? Since SOD(4444^4444) is a single digit number, then SOD(4444^4444) should be the same as SOD(SOD(4444^4444)).

Anyways, without going through all the work above.... just know that SOD(n) = n mod 9.

"n mod 9" means if you divide "n" by 9, the remainder is the modulus. So... the sum of digits of a number is equal to the remainder of dividing the number by 9.

If you want to cheat, here's a quick and easy formula to use in PHP for SOD(x^y):

$sod = bcmod(bcpow(x, y), 9);

For example: bcmod(bcpow(4444, 4444), 9);

[ QUOTE ]
This was in a math puzzle book I own. The explanation made no sense to me. I'm curious if anyone can figure this one out. I'll post the answer to it sometime tomorrow or the day after. Good luck.

[/ QUOTE ]


SOD = sum of digits. Therefore, SOD(356) = 3 + 5 + 6 = 14.

What is SOD(SOD(SOD(4444^4444)))?

[/ QUOTE ]
The SOD operation is invariant mod 9.

Now, 4444 is equivalent to 7 mod 9.
And the totient of 9 is 6.
And 4444 is equivalent to 4 mod 6.
So 4444^4444 is equivalent to 7^4 mod 9.
Now, 7^4 is equivalent to 7 mod 9.

So SOD(SOD(SOD(4444^4444))) is equivalent to 7 mod 9.

Now, 4444^4444 has at most 4444*5=22220 digits which can be at most 9 each, so we're looking at SOD(4444^4444) must be less than or equal to 199,990. That means that SOD(SOD(4444^4444)) must be less than or equal to 45 (the largest SOD up to 199,990). Then SOD(SOD(SOD(4444^4444))) is going to be less than or equal to 12.

Now, we're looking for a number that is less than or equal to twelve, and equivalent to 7 mod 9. 7 is the only such number.

[kyro]

wow. you guys can all burn in hell. talk about a deflated ego.

Here's a similar one:

How many consective 0's (not total 0's) are at the end of the number 1,000,000!

For instance, there are two consecutive 0's at the end of the number 305400

[ QUOTE ]
Here's a similar one:

How many consective 0's (not total 0's) are at the end of the number 1,000,000!

For instance, there are two consecutive 0's at the end of the number 305400

[/ QUOTE ]
Didn't realise ! was factorial for a second...thought you were rubbing it in [img]/images/graemlins/smile.gif[/img]

Start with 1, and multiply by 2, 3, ... 1,000,000.

Each time you multiply by a number ending in 0, it adds a zero. Any time you multiply a number where the last (rightmost) nonzero number is even by 5, the product has an extra zero. As we ascend through the sequence, that number will always be even, because we'll be multiplying it by even numbers.

Count the number of 5's and 0's, and get 2 x (1,000,000)/10 = 200,000

Here's a harder version of the original problem: what are SOD(SOD(4444^4444)) and SOD(4444^4444)?
Note: SOD(SOD(x)) is not identical to SOD(x). SOD(365) = 14; SOD(SOD(365)) = 5.

[ QUOTE ]
200,000

[/ QUOTE ]

nope