Fun with Exponents

[jay_shark]

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

[Silent A]

"00000", if we use base 9 units.

That was easy.

[jay_shark]

lol

[Arp220]

||||9

(the '|'s are upward pointing arows)

is this cheating?

[Dale Dough]

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..

[jay_shark]

Very entertaining post Dale .

Your answer is crazy, but right !!

[Dale Dough]

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!

[molotom]

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

[Dale Dough]

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.

[bigpooch]

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?