Fun with Exponents
 

Find the last 5 digits of 9^9^9^9^....^9 which contains 2007 9's .

Re: Fun with Exponents
 

"00000", if we use base 9 units.

That was easy.

Re: Fun with Exponents
 

lol

Re: Fun with Exponents
 

||||9

(the '|'s are upward pointing arows)

is this cheating?

Re: Fun with Exponents
 

EDIT: If this post conveys too much confidence, I didn't mean it. It's merely my best guess. Answer at the bottom.

OK, this is a very very un-mathematical method.. I made an excel sheet with a function that multiplies five digits by 9, and then takes the modulus 100k, so it will always remain five digits.

Turns out this function has a period of 2500 iterations (is that the right terminology?). In other words, 9^2500 ends in 00001, as does 9^5k, 9^7500 etc. I verified this with Mathematica.

(The fact that I use this method to solve the problem probably means I don't deserve to have Mathematica, but that's another discussion [img]/images/graemlins/smile.gif[/img])

So, it's one of 2500 possibilities.

How big is 9^9^9^9.. with 2007 nines? I'm gonna assume that the formula is evaluated right to left, ie. 9^(9^(9^.. etc. Prolly standard for most, but again I'm a noobie.

We probably don't need to know. Since the last five digits repeat every 2500 iterations, all I need is 9^... with 2006 nines, mod 2500. Yay! Once we know which it is, we can take the last five digits of 9^(whatever that number).

It turns out that this function has a period of 250. So, our 2500 options are cut down to 250.

The period of 9^x mod 250 is 50.

(using the same Excel method)

Period of 9^x mod 50: 10

Period of 9^x mod 10: 2

Recap: We start with 100k options. We cut this down to 2500 possible combinations of the last five digits of 9^x.. 9^2500 mod 100k = 9^0 mod 100k = 1.

Because I barely understand this myself, and I assume somebody knows the answer, I won’t go into too much detail; I don’t expect anyone who didn’t understand before to understand it now.

The formula I get is:

9^( 9^( 9^( 9^( 9^( 9^(gazillion) mod 2) mod 10) mod 50) mod 250) mod 2500) mod 100k

Solving step by step: 9^gazillion mod 2 = 1, so we get:

9^( 9^( 9^( 9^( 9^(1) mod 10) mod 50) mod 250) mod 2500) mod 100k

Step 2: ( 9^(1) mod 10) = 9, so

9^( 9^( 9^( 9^9 mod 50) mod 250) mod 2500) mod 100k

Step 3: ( 9^9 mod 50) = 39

9^( 9^( 9^39 mod 250) mod 2500) mod 100k

Step 4: 9^39 mod 250 = 39

9^( 9^39 mod 2500) mod 100k

Step 5: 9^39 mod 2500 = 289

9^289 mod 100k = 45289

Cliff Notes: 45289. That’s my final answer.

I probably didn’t use the most elegant method to solve this problem; it probably can (and should) be done without long tables in Excel, and Mathematica. I’d be interested to hear a better method. Provided of course I didn’t get it wrong, period..

Re: Fun with Exponents
 

Very entertaining post Dale .

Your answer is crazy, but right !!

Re: Fun with Exponents
 

That's one out of two. Glad I didn't completely waste my too lazy to play cards time.

I will take your calling my answer crazy as a confirmation that there does in fact exist a more elegant, likely not computer-intensive, solution. I'm curious now!

Re: Fun with Exponents
 

Not exactly elegant, but here goes:

Lemma:
9^10 = 1 mod 100
9^100 = 1 mod 1000
9^1000 = 1 mod 10000
etc

Let f(n) = 9^9^...^9 containing n nines.

f(1) = 9 = -1 mod 10
f(n+1) = f(1)^9 = (-1)^9 = -1 mod 10
So f(n) = -1 mod 10 , for all n>1. Therefore the last digit is 9.

Now for n>2:
f(n) = 9^f(n-1) = 9^(10a + b) where b = f(n-1) mod 10
But 9^10 = 1 mod 100 (by lemma), and f(n-1) = -1 mod 10, therefore:
f(n) = 9^b = 9^(-1) = -11 = 89 mod 100

Similarly
f(n) = 9^89 = 289 mod 1000

f(n) = 9^289 = 5289 mod 10000

f(n) = 9^5289 = 45289 mod 100000

Note that this holds for all n > 5

Re: Fun with Exponents
 

Thanks. I'm gonna hit Wikipedia now to see if I can get to a point where I understand all that.

PS I blame this thread for at LEAST two hours of forgone +EV at the tables tonight.

Re: Fun with Exponents
 

Do you have a very "elegant" solution? Why not the last six
digits?

First off, if there is a "tower of nines" by exponentiation,
and the last d digits are to be found (where d is small
enough), the question is equivalent to one where the "tower"
only has 3d-3 nines (the reason being that 9 is congruent
to 1 when the modulus 2^3=8 is eventually attained) by
successive application of Euler's theorem where a^phi(m) is
congruent to 1 (mod m) because the moduli are products of
powers of 2 and 5 whereas the base a is some power of 3.

By "going up" the tower, the moduli are reduced from 10^d =
(5^d)(2^d) to (2^2)(5^(d-1))(2^(d-1)), ... , 2^2d,
2^2d-1, ..., 2^3.

Secondly, 9^9^9^x = 9 (mod 32) by successive application of
Fermat's little theorem where x is a "smaller tower"
[x=1 mod 8 so 9^x = 9 (mod 16) so 9^9 = 9 (mod 32). It
also turns out that also 9^9 = 9 (mod 64) so why not six
digits? ] Thus, congruence to 9 (mod 32) holds.

The above seems to be a start of a better solution although
I don't yet see the idea for the moduli starting with 5^5.
It's true that in two steps you get to 1000 and it's quite
easy to find the last three digits from there. The other
interesting observation is that 9^289 = 289 (mod 5^4).

In any case, it seems that a very elegant solution has
eluded some of us.

Also, did you check the lemma used in the other post?

Re: Fun with Exponents
 

One way of doing this is to expand (10-1)^9 using the binomial theorem . This should be easy to do and you can determine very easily that the last two digits are 89 .

z1=9
z2=(10-1)^9 = 10^z1 - z1c1*10^(z1-1) +...z1c(z1-1)*10 -1
last two digits are 90-1=89 since z1=9 .


Now expand z3= [(10-1)^9]^9 again using the binomial theorem and using the fact that the last two digits of (10-1)^9 is of the form ...89 .The last 3 digits should be easy to find . You should arrive at -600+890 -1 =289

The last 4 digits of z4 = 4000-1600 +2890-1 =5289

The last 5 digits of z5 = -60000 +640000-11600+52890 -1 =45289 .

After this point it keeps on repeating and the answer becomes obvious .

Re: Fun with Exponents
 

You beat me to the punch! I was just about to post the
binomial solution.

Re: Fun with Exponents
 

If x is some "tower of nines" and with the notation for z[j]
as in your post, this is just to clarify (perhaps for any
readers out there):

Since x is odd, with C(n,r) denoting the combinations of n
choose r,

[10-1]^x = (-1) + C(x,1)*10 - C(x,2)*100 + C(x,3)*1000 - ...

so

z1 = -1
= 9 (mod 10)

z2 = -1 + C(9,1)*10 = -1 + 90
= 89 (mod 100)

z3 = -1 + C(89,1)*10 - C(89,2)*100 = -1 + 890 - 600
= 289 (mod 1000)

z4 = -1 + C(289,1)*10 - C(289,2)*100 + C(289,3)*1000
= -1 + 2890 - 1600 + 4000
= 5289 (mod 10000)

z5 = -1 + C(5289,1)*10 - C(5289,2)*100 + C(5289,3)*1000
-C(5289,4)*10000
= -1 + 52890 - 11600 + 64000 - 60000
= 45289 (mod 100000)