wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> 9^9^..ad infinitum
        
(Message started by: TenaliRaman on Mar 1st, 2004, 6:25am)
Title: 9^9^..ad infinitum
Post by TenaliRaman on Mar 1st, 2004, 6:25am
Let x=9^9^9^...ad infinitum
Find the last ten digits of x.

Unfortunately,my elementary modular arithmetic skills haven't helped me here and this seems too daunting to be executed on a computer.

Seeing that this was on my College Puzzle Board, i am expecting it to be easy.
Title: Re: 9^9^..ad infinitum
Post by Barukh on Mar 1st, 2004, 6:47am
I'm confused... Is x a finite number? Or I misunderstand the meaning of '^' operation?
Title: Re: 9^9^..ad infinitum
Post by John_Gaughan on Mar 1st, 2004, 6:52am
:: [hide]0123456789[/hide] ::
Title: Re: 9^9^..ad infinitum
Post by THUDandBLUNDER on Mar 1st, 2004, 7:01am

Quote:
I'm confused...

That makes three of us.  :D (Evidently John is not.)
Title: Re: 9^9^..ad infinitum
Post by towr on Mar 1st, 2004, 7:09am

on 03/01/04 at 06:25:08, TenaliRaman wrote:
Let x=9^9^9^...ad infinitum
Find the last ten digits of x.

I suppose you mean something like
f1 = 9
fn = fn-1^9
gn = fn % 10000000000
and we should find lim n [to] [infty] g(n)
Rather than trying to find (lim n [to] [infty] f(n)) % 10000000000 = [infty] % 10000000000 which is undefined

You can use
h1 = 9
hn = hn-1^9 % 10000000000
to find the answer, since the 11th (or higher) least significant digit won't affect the lesser significant digits in these kind of multiplications..

But it doesn't seem to converge..
Title: Re: 9^9^..ad infinitum
Post by rmsgrey on Mar 1st, 2004, 7:51am
Does fn=9^fn-1 give convergence on gn?
Title: Re: 9^9^..ad infinitum
Post by towr on Mar 1st, 2004, 7:59am
I was just thinking about that..
I'm not sure how to get an answer (if there is one) in that case though..
Title: Re: 9^9^..ad infinitum
Post by John_Gaughan on Mar 1st, 2004, 8:13am

on 03/01/04 at 07:01:56, THUDandBLUNDER wrote:
That makes three of us.  :D (Evidently John is not.)

My answer is speculation based on inspection of the first few results. Obviously the number gets very large very quickly, so without some sort of proof, there is no way to know for sure.
Title: Re: 9^9^..ad infinitum
Post by John_Gaughan on Mar 1st, 2004, 8:19am
How about representing 910 in base 3 (1003) or 9 (109)? Essentially the problem then becomes: given a number in base 3 or 9 that is a 1 with an infinite number of zeros after it, what are the last ten digits in base 10?
Title: Re: 9^9^..ad infinitum
Post by Sameer on Mar 1st, 2004, 8:22am
hmmm I think this one goes with that thread of .999... = 1 thing I guess..

:: [hide]
Here's my approach Let's say the last ten digits were represented by number m.

Let m be broken up into 10 digits a1,a2,... a10.

Then a10*9 = a10 (since it converges?) => a10 = 0
Recursively all numbers come to 0.

So the answer is 0000000000

[/hide] ::
Title: Re: 9^9^..ad infinitum
Post by towr on Mar 1st, 2004, 9:16am
I very much doubt you can ever get 9^x to end in 0..
Title: Re: 9^9^..ad infinitum
Post by Sameer on Mar 1st, 2004, 9:47am
Crap you are right.. I just modified the problem from powers to multiplicated  :'( .. back to drawing board... looks like any number raised to power 9 can have the last number as itself... so i guess u just work backwards...
Title: Re: 9^9^..ad infinitum
Post by John_Gaughan on Mar 1st, 2004, 11:04am

on 03/01/04 at 09:16:50, towr wrote:
I very much doubt you can ever get 9^x to end in 0..

9x must end in 1 or 9. Think. 92 = 81. Multiply 81 by 9, and the last digit clearly is 9. Again, 9 times 9 is 81. The last digit at least must equal 1, although carrying means the 10s digit may not equal 8.

Of course, since this is 99 and not 92, the answer will be more restrictive -- either one or nine. I suspect it will be nine. And I still think my first guess is correct.

The cycle goes on and on... where does it end? It does not!
Title: Re: 9^9^..ad infinitum
Post by John_Gaughan on Mar 1st, 2004, 11:16am
I ran this simple little C++ program and it just keeps scrolling and scrolling, apparently disregarding the overflow bit, and never comes to any conclusion. Maybe that is the problem -- some inaccuracy introduced from overflowing and blundering forward anyway.

that integer type is G++'s 64 bit unsigned integer. It is not standard. I think MS VC++ calls it "int64" or "_int64".


Code:
#include <iostream>
using namespace std;

int main (void)
{
 unsigned long long int n;
 unsigned long long int mask = 10000000000;
 for (n = 9; n < ULONG_LONG_MAX; n = n * n * n * n * n * n * n * n * n)
 {
   cout << (n % mask) << endl;
 }
 return 0;
}
Title: Re: 9^9^..ad infinitum
Post by THUDandBLUNDER on Mar 1st, 2004, 11:18am
John, the last digit of 92n+1 is indeed 9 for any positive integer n.


Quote:
Let x=9^9^9^...ad infinitum

But 9[smiley=infty.gif] is not an integer and therefore has no final digit(s).  ::)
We can't even claim that the final digit is 9.  

Title: Re: 9^9^..ad infinitum
Post by towr on Mar 1st, 2004, 11:18am
The last digit will allways be 9, since 9 is odd, 9^9 is odd and ends in a 9 etc.. As long as fn-1 is odd, 9^fn-1 = fn must end with a 9 (and is thus odd)

But how do we get the other numbers?
Title: Re: 9^9^..ad infinitum
Post by John_Gaughan on Mar 1st, 2004, 11:41am

on 03/01/04 at 11:18:50, towr wrote:
The last digit will allways be 9, since 9 is odd, 9^9 is odd and ends in a 9 etc.. As long as fn-1 is odd, 9^fn-1 = fn must end with a 9 (and is thus odd)

But how do we get the other numbers?

We have the initial case, now all we need is the inductive step ;-)

I figured that the last digit will always be 9, I was talking about other powers though, in response to another post.
Title: Re: 9^9^..ad infinitum
Post by John_Gaughan on Mar 1st, 2004, 11:43am

on 03/01/04 at 11:18:38, THUDandBLUNDER wrote:
But 9[smiley=infty.gif] is not an integer and therefore has no final digit(s).  ::)

Just like 0.9999999... is not 1, right? It has no final digits, at least not toward the unit's place, right? ::)
Title: Re: 9^9^..ad infinitum
Post by kellys on Mar 1st, 2004, 11:45am
9-adically, x=0
Title: Re: 9^9^..ad infinitum
Post by THUDandBLUNDER on Mar 1st, 2004, 12:09pm

on 03/01/04 at 11:43:54, John_Gaughan wrote:
Just like 0.9999999... is not 1, right? It has no final digits, at least not toward the unit's place, right? ::)

A different kettle of fish altogether.
0.9999... represents a convergent series which sums to the finite number of 1. No problem there.
Whereas we have a tower of exponents whose value diverges to an infinite number as it gets taller.

Are you still claiming that the final digit of ((((((9^9)^9)^9)^9)^9)^)^..... is 9?

Or do you mean, to paraphrase your sig, that the last digit of ((((((9^9)^9)^9)^9)^9)^)^..... is 9
for large values of  ((((((9^9)^9)^9)^9)^9)^)^.....?  :D
Title: Re: 9^9^..ad infinitum
Post by John_Gaughan on Mar 1st, 2004, 12:19pm
The last three digits are [hide]489[/hide]. Let's see if you can figure out the rest :-)

edit: ah crap, that is not it... but I am close, I swear!
Title: Re: 9^9^..ad infinitum
Post by THUDandBLUNDER on Mar 1st, 2004, 12:21pm
OK, the answer is [hide]......489[/hide]
What is the question?

If the question is 'What are the last three digits of (((((((9^9)^9)^9)^9)^9)^9)^9)^9
then the answer is ...089

And the last ten digits are ...9107814089

8)
Title: Re: 9^9^..ad infinitum
Post by Sameer on Mar 1st, 2004, 1:10pm
how did you arrive at this answer?
Title: Re: 9^9^..ad infinitum
Post by THUDandBLUNDER on Mar 1st, 2004, 1:20pm

Quote:
how did you arrive at this answer?

I had a peek at John's screen just as his numbers stopped 'scrolling and scrolling' and then quickly checked the answer with Mathematica.  
:)

What are the first few digits of 9^(9^(9^9))?
How feasible would it be to calculate them?
What would be your best guess for the 1st digit?
What else can be said about this number? (Yes, I know it's big.)
Title: Re: 9^9^..ad infinitum
Post by John_Gaughan on Mar 1st, 2004, 1:32pm

on 03/01/04 at 13:20:29, THUDandBLUNDER wrote:
I had a peek at John's screen just as his numbers stopped scrolling and scrolling and then I quickly checked the answer with Mathematica.

I answered several questions that this thread did not ask in the process of writing that little program. It still is not correct. I really need to pay attention either to riddles or to my job, but not both at the same time ;-)
Title: Re: 9^9^..ad infinitum
Post by Sameer on Mar 1st, 2004, 3:07pm

on 03/01/04 at 13:20:29, THUDandBLUNDER wrote:
What are the first few digits of 9^(9^(9^9))?


The first few digits are 4393285036 ...

The last few are ...9118815689

still doenst tell my anything.. besides the fact that the total number of 9's i raised to is the first digit in first few digits part .. and that
91 .... 89  in the last few match up with your answer  ???
Title: Re: 9^9^..ad infinitum
Post by THUDandBLUNDER on Mar 1st, 2004, 3:10pm
Sameer, you have mistakenly computed ((9^9)^9)^9 instead of (mistakenly) computing 9^(9^(9^9)).   ::)
Title: Re: 9^9^..ad infinitum
Post by Sameer on Mar 1st, 2004, 3:15pm

on 03/01/04 at 15:10:46, THUDandBLUNDER wrote:
Sameer, you have mistakenly computed ((9^9)^9)^9 instead of (mistakenly) computing 9^(9^(9^9)).   ::)


crap I can't do that.. enlighten me please ???
Title: Re: 9^9^..ad infinitum
Post by THUDandBLUNDER on Mar 1st, 2004, 3:36pm

on 03/01/04 at 15:15:11, Sameer wrote:
crap I can't do that.. enlighten me please

Haemorrhoids?
Title: Re: 9^9^..ad infinitum
Post by towr on Mar 1st, 2004, 3:50pm
7392745289 seems like a nice value..
I'm just not sure if the way I got it was valid..  ::)
Title: Re: 9^9^..ad infinitum
Post by Eigenray on Mar 1st, 2004, 4:50pm
First note that for odd k, 9k = (10-1)k = 10k-k10k-1+... -C(k,2)x102+kx10-1.
Now let's consider the sequence a1=9, ak+1 = 9ak.
a1 = 9 mod 10.
a2 = 9a1 = 10a1 -1 = 89 mod 100.
a3 = 9a2 = -a2(a2-1)/2.100 + a2.10 - 1 = -9.8/2.100 + 890 - 1 = 289 mod 1000.
a4 = 9a3 = a3(a3-1)(a3-2)/6.1000 - a3(a3-1)/2.100 + a3.10 - 1 = 9.8.7/6.1000 - 89.88/2.100 + 289.10 - 1 = 4000 - 1600 + 2890 - 1 = 5289 mod 104
And so on, until we get that a10 = 7392745289 mod 1010.
Now, the value of ak+1 = 9ak modulo 1010 only depends on the value of ak modulo 109, so it follows inductively that a10 = a11 = a12 = ... = 7392745289 mod 1010.
Title: Re: 9^9^..ad infinitum
Post by Icarus on Mar 1st, 2004, 5:22pm
Anything involving infinity, you know I have to comment on... But you all have taken the main points. But since I like to hear myself talk (read myself type?), I'll reiterate.

The original problem, as stated, has no answer for the simple reason that the sequence does not converge, so it's limit does not have "10 last digits".

The best reinterpretation in my opinion is ONE OR THE OTHER of these: what is the limitn[to][subinfty] fn % 1010, where either f1 = 9 and fn = fn-1^9 OR f1 = 9 and fn = 9^fn-1. Polypowers are not commutative or associative. The two cases may give different answers.

Kellys gives a third interpretation. x does not exist as a Real number but it does exist in the n-adics. In particular, x may be viewed as a 10-adic (rather than the trivial 9-adic version), in which case the original question is quite sensible. Except that it still is ambiguous about the meaning of 9^9^9^... Is this an ascending or descending polypower? For those not familiar with n-adic numbers, there is a thread about them in the hard section.

And TenaliRamen, I am afraid your expectation is wrong. Sometimes people like to throw a ringer in. Though in this case, I think they should of specified their meaning. (Or perhaps their answer is the "does not exist" one.)
Title: Re: 9^9^..ad infinitum
Post by John_Gaughan on Mar 1st, 2004, 7:16pm

on 03/01/04 at 17:22:53, Icarus wrote:
Except that it still is ambiguous about the meaning of 9^9^9^... Is this an ascending or descending polypower?

Order of operations:
((((9^9)^9)^9)^9)...
Powers are evaluated left to right. Or is it right to left? ;-)
Title: Re: 9^9^..ad infinitum
Post by Eigenray on Mar 1st, 2004, 9:23pm

on 03/01/04 at 17:22:53, Icarus wrote:
The best reinterpretation in my opinion is ONE OR THE OTHER of these: what is the limitn[to][subinfty] fn % 1010, where either f1 = 9 and fn = fn-1^9 OR f1 = 9 and fn = 9^fn-1. Polypowers are not commutative or associative. The two cases may give different answers.


Indeed, for fn=9^fn-1, the limit exists, while if fn=fn-1^9, it does not:
Claim 1: If x=9 mod 100, x9=89 mod 100.
(100k + 9)9 = 99 = (10-1)9 = 9.10 - 1 = 89 mod 100.
Claim 2: If x=89 mod 100, x9=9 mod 100.
(100k + 89)9 = (-11)9 = -(10+1)9 = -(9.10+1) = 9 mod 100.
It follows that f2k = 89 mod 100, while f2k+1 = 9 mod 100.  Since {fn%102} doesn't converge, {fn%1010} can't either.
Title: Re: 9^9^..ad infinitum
Post by TenaliRaman on Mar 1st, 2004, 11:19pm
The above discussion has put my mind at ease. When i complained to the puzzle mgmt committee (which consists of actually a group of students only) that the question was at err, i got a reply like this "the source from where we got the question says that there is a solution".To which i replied "ok i give up give me the solution".Their reaction "unfortunately we lost the source from where we got the answer and hence the solution". My reaction  >:( . Well c'est la vie.

Anyways i loved the variation provided by towr which led to an answer from both (towr and eigenray)!! (Cool!!)
Title: Re: 9^9^..ad infinitum
Post by THUDandBLUNDER on Mar 2nd, 2004, 1:45am

on 03/01/04 at 15:50:06, towr wrote:
7392745289 seems like a nice value..

...for what?
Title: Re: 9^9^..ad infinitum
Post by towr on Mar 2nd, 2004, 2:02am

on 03/02/04 at 01:45:39, THUDandBLUNDER wrote:
...for what?
Oh, I dunno.. An answer the supposed question perhaps? Which is what this thread is about after all..
Title: Re: 9^9^..ad infinitum
Post by THUDandBLUNDER on Mar 2nd, 2004, 2:19am

on 03/02/04 at 02:02:32, towr wrote:
Oh, I dunno.. An answer the supposed question perhaps? Which is what this thread is about after all..

There was more than one question posed in this thread.

(Sorry, what does % 1010 mean?)
Title: Re: 9^9^..ad infinitum
Post by towr on Mar 2nd, 2004, 3:31am
a % b [equiv] mod(a,b)
q = a % b => a = k * b + q, where 0 [le] q < b, k [in] [bbz]
It's a convention in many programming languages and mathematical packages.. (Though there is some disagreement for cases where sign(a) = -sign(b), as to wether q should be positive or negative)

As for which question 7392745289 is an answer to; it was quickly shown the original question has no answer, so it would stand to reason that's not the one.
Of the variants
limit n [to] [infty] fn % 1010
The one with f1 = 9 and fn = fn-1^9 was allready shown not to converge, so again it stands to reason this wasn't the one.
So the answer would be to the last variant, where f1 = 9 and fn = 9^fn-1 And in the post after mine Eigenray showed how to get this answer in a responsible way.
(I used limit n [to] [infty] hn
with h1 = 9 and hn = 9^hn-1 % 1010
without knowing for sure wether that should give the correct answer)
Title: Re: 9^9^..ad infinitum
Post by Icarus on Mar 2nd, 2004, 3:30pm
Yes, and by the way, under the one interpretation for which the original question works, (x is a 10-adic, not real, number), the answer will be the same.

And, TenaliRamen, you can tell those responsible for this puzzle that either their source stated it poorly, or else THEY messed it up in posting it, but either way, as it is, the solution is trivial. x = [infty] and so does not have any "last ten digits".

However, with a little clean-up, it does make a nice puzzle.
Title: Re: 9^9^..ad infinitum
Post by THUDandBLUNDER on Mar 3rd, 2004, 4:18am

Quote:
So the answer would be to the last variant...

...or to the variant after the 'last' one, which was:


on 03/01/04 at 13:20:29, THUDandBLUNDER wrote:
What are the first few digits of 9^(9^(9^9))?


Title: Re: 9^9^..ad infinitum
Post by towr on Mar 3rd, 2004, 4:46am

on 03/03/04 at 04:18:35, THUDandBLUNDER wrote:
Or to the variant after the 'last' one, which was
'last' referred to "variants with limit n [to] [infty] fn % 1010"

Besides I don't really think  9^(9^(9^9)) could reasonably have been the 'real' question as intended with the original question (which itself was obviously not what it was meant to be).
Yours is more of new question than a variant of the original (it neither has an infinite power tower, nor looks at the last digits) And in case you're wondering, I don't have an answer for it..


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board