wu :: forums - Print Page


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

        riddles >> hard >> Finite Math; x^x^x
        
(Message started by: Troy I. on Dec 5^th, 2002, 10:19am)

Title: Finite Math; x^x^x
Post by Troy I. on Dec 5^th, 2002, 10:19am

sqrt(2)^sqrt(2)^sqrt(2)=2.
Since if you let x=sqrt(2)^sqrt(2)^sqrt(2) then x=sqrt(2)^x and it is easy to see then that if x=2 then the equation is true.
What is the largest value for x such that x^x^x represents a finite value?
What is that value?
??? ??? ???
We could really use some help on this, if anyone wouldn't mind, thank you

Title: Re: Finite Math; x^x^x
Post by Garzahd on Dec 5^th, 2002, 10:40am

There are some pretty darn large x for which x^x^x is finite.

Perhaps you mean irrational x for which x^x^x is rational?

Title: Re: Finite Math; x^x^x
Post by TimMann on Dec 5^th, 2002, 11:04am

I think Troy I. is trying to say x^x^x... That is, the limit of the sequence x, x^x, x^x^x, x^x^x^x, ... That's the only way to make sense out of what he wrote about the x=sqrt(2) case.

Title: Re: Finite Math; x^x^x
Post by James Fingas on Dec 5^th, 2002, 12:12pm

Tim, I think you're right. At first, I thought he meant

(sqrt(2)^sqrt(2))^sqrt(2) = 2

which is true, but not very interesting. However, the limit of the exponentials thing is cool. Of course the answer involves our favourite number e. I also found some of the limits of spreadsheet simulation :(

The correct value was trickly to spot in my simulation since I only ran 6000 or so levels of exponentiation. The real sequence approaches its limit amazingly slowly. After calculating 42000 levels of exponentiation, I can still only see three decimal places of accuracy in the limit.

Of course I'm not going to say what the answer is since I just brute-forced it.

Title: Re: Finite Math; x^x^x
Post by James Fingas on Dec 5^th, 2002, 2:05pm

This is a really cool problem! Now for some extra stuff:

What is the smallest number so that the series x, x^x, x^x^x, ... converges? What does it converge to?

What is the derivative of the limit of the series x, x^x, x^x^x, ... with respect to x, evaluated at the largest value of x which causes the series to converge?

For what values of b does b, b^x, b^x^x, b^x^x^x, ... converge? Of course, this will be a function of x :)

Title: Re: Finite Math; x^x^x
Post by SWF on Dec 5^th, 2002, 6:59pm

Let y=x^(x^(x^.... = x^y
x=y^1/y
dx/dy=0 when y=e, so maximum x is e^1/e.

Title: .)Re: Finite Math; x^x^x
Post by Icarus on Dec 5^th, 2002, 9:11pm

SWF brings up an important distinction: ^ is not commutive nor associative, so it makes a difference how you interpret x^x^x... . Is x^x^x... = x^(x^(x^..., or is it = ...(((x^x)^x)...?

More exactly, we have these two sequences:

(Descending) x_n = x^x_n-1
(Ascending) x_n = x_n-1^x

(For example: (sqr(2)^sqr(2))^sqr(2) = 2, just as James says, but sqr(2)^(sqr(2)^sqr(2)) ~ 1.76.)

I seems to me that James meant ascending in his b^x^x^... question, since the descending (b then x) sequence is just b raised to descending x sequence. I.e., not an interesting variant.

SWF's result however is on the descending sequence.

Sequences like these are called Polypowers, which is all I remember off-hand of Martin Gardner's article on them.

Title: Re: Finite Math; x^x^x
Post by Chronos on Dec 6^th, 2002, 12:19am

For sake of notational sanity, you should do it the way SWF has it. If you consider x^x^x to mean (x^x)^x, then you might as well just write x^(x^2). By this interpretation, x^x^x^x... is equivalent to x^(x^oo), which will diverge for all x>1, and give you 1 for all x <= 1.

Title: Re: Finite Math; x^x^x
Post by Icarus on Dec 6^th, 2002, 10:02am

True. I had not noticed how trivial the ascending case is. This still leaves the question of what James' point with the b^x^... sequence is. For ascending sequence the answer is only b=0 converges if x>1, and it converges for all b if x <= 1. On the other hand, for the descending sequence, b^x^x^... converges for all b if x^x^x^... converges, by the continuity of exponentiation. (I'm assuming b, x >= 0 since we don't want to mess with complex multivalued functions.)

Title: Re: Finite Math; x^x^x
Post by James Fingas on Dec 9^th, 2002, 9:59am

Sorry about my last question there. This problem is still not intuitive to me (I don't know how the rest of you feel about it).

What I meant to say was:
For what values of b does the sequence b, x^b, x^x^b, x^x^x^b, ... converge to a finite value? Of course, this will depend on the value of x. The answer to the other one was "any finite b, supposing that x, x^x, x^x^x, ... converges", but it was trivial.

Title: Re: Finite Math; x^x^x
Post by Icarus on Dec 9^th, 2002, 7:35pm

I wondered if that was what you meant, and no, this is not intuitive to me either. I actually twice started to post a "proof" that the sequence does not converge for x > 1 (SWF's calculation assumes convergence), before I finally realized my error. So I have been examining convergence more carefully. This is what I have found so far:

1) if x > 1, then x_n = x^x_n-1, x₁ = x, is an increasing sequence. Let E=e^1/e. If x <= E, then x_n <= E_n < e for all n. Thus {x_n} is a bounded increasing sequence, and so must converge.

2) if 0 < x < 1, then 0 < x_n < 1 for all n, {x_2n} is a decreasing sequence, {x_2n+1} is an increasing sequence, and x_2n > x_2m+1 for all n,m. Thus the even and odd subsequences both converge, with the limit of the even sequence >= the limit of the odd. The full sequence converges if and only if these two limits are equal. Both of these limits satisfy the equation y=x^{x^y}. ~~This equation has either 0 or 2 solutions for y (depending on the value of x) with a single solution for y at the boundary between these two regions.~~

I suspect, but have not proven, that both subsequences will converge to the same solution whenever solutions are available (i.e., one solution is an attractor, while the other solution is a repeler). If so, the "boundary value" where y has a single solution is the minimum value of x for which x^x^x^... converges.

Title: Re: Finite Math; x^x^x
Post by SWF on Dec 9^th, 2002, 9:09pm

Quote:

For what values of b does the sequence b, x^b, x^x^b, x^x^x^b, ... converge to a finite value?

Let y= ...x^x^x^b = x^y. Similar reasoning to that given above for x^x^x^... above says that if x<=e^1/e, y<=e. But if x>e^1/e, then y is not finite.

If b<=e then any x<=e^1/e ensures that b, x^b, x^x^b, x^x^x^e, ... are all <= e so it converges.

If b>e, then x needs to be small enough that b, x^b, x^x^b, x^x^x^b, is a non-increasing sequence, i.e. x^b<=b, or x<=b^1/b

So for the sequence to converge, if b<=e, x needs to be less e^1/e, or
if b>e, x needs to be <=b^1/b.

Title: Re: Finite Math; x^x^x
Post by James Fingas on Dec 10^th, 2002, 9:51am

SWF,

Very good. That answers all of my questions except for the first one: What is the smallest x so that x, x^x, x^x^x, ... converges?

Icarus,

That is an interesting analysis for 0 < x < 1. The convergence behaviour of the subsequences is very interesting near the minimum value for which the overall sequence converges. Do you know yet what that value is?

Title: Re: Finite Math; x^x^x
Post by SWF on Dec 10^th, 2002, 6:46pm

Please excuse my lack of rigor. Although the derivations may be less than convincing, I believe the expressions I am coming up with are the correct answers.

For x^x^x^... to not converge to a single value with 0<x<1, the alternate terms in the sequence x, x^x, x^x^x,... will approach two different values L and M. For the alternate terms to do this x^L=M and x^M=L. So ln(x)=ln(M)/L=ln(L)/M. Or M*ln(M)=L*ln(L). The smallest value of for the function z*ln(z) that does not permit multiple solutions M and L occurs at the local minimum, z=1/e. Plugging this value in for L and M in the above expression for ln(x) gives: ln(x)=e*ln(1/e), or x=(1/e)^e=e^-e. This is the minimum x such that x^x^x^... converges. There is an interesting similarity to the form of largest value of x that results in convergence.

Title: Re: Finite Math; x^x^x
Post by Icarus on Dec 10^th, 2002, 7:10pm

The value I get is e^-e.

I was sidetracked for a while by a calculation mistake. I had messed up taking the derivative of y=x^x^t with respect to t, and as a result I thought the second derivative was always positive and the graph concave upward, which gave me the bit about y=x^x^y having only 0, 1, or 2 solutions (with 1 only at the boundary between 2 and 0). This was wrong. In fact for 0 < x < 1, the graph of y=x^x^t in the t-y plane looks similar to y=(arctan(x)+1)/2. That is: asymptotic to y=0 from above on the negative side, asymptotic to y=1 from below on the positive side, with a single inflection point somewhere in the middle.

The derivative of y=x^x^t is y' = yx^tln²x.
Also, y'' = yx^tln³x(x^tln x + 1).
y and x^t are positive and ln x is negative, and x^tln x + 1 is negative to left of t = -ln(-ln x)/ln x (equivalently, y = 1/e) and positive to the right, so the curve rises from 0 at -oo concave up until it passes through the inflection point at y=1/e, then it continues to increase concave down as it approaches 1 at +oo. Decreasing the value of x increases the slope of the curve at its inflection.

For large values of x, the slope is < 1, and the curve intersects y=t at only one point, providing a single solution to y=x^x^y. For smaller x the slope > 1, and the curve will cross y=t 3 times: 1st near y=0 as it comes in from -oo, 2nd as it rises towards the inflection point, and 3rd near y=1 as it goes towards +oo. As x continues to decrease, both the lower two points go to 0, while the upper point approaches 1.

Thus the equation y=x^x^y for x < 1 has either 1 or 3 solutions. When there is only one solution, the two subsequences must both converge to it, so the full sequence converges to it as well. When there are three solutions the lower subsequence converges to the lowest solution, while the upper subsequence converges to the highest solution, so the full sequence diverges.

The minimum value of x for which the sequence converges is thus the value where the single solution of y=x^x^y splits into 3: where the slope of y=x^x^t is 1 at the inflection point, which lies on y=t. This turns out to be x = e^-e.

I'm sure there are easier ways to find that answer, but this one developed for me a clear understanding of why, so I'm happy with it. :)

Edited to add: SWF slipped in with an easier derivation while I was typing in my opus.
Edited again to correct a math error.