Welcome to MathOverflow

Question

18

8

For what positive x's the number of distinct values taken by x^x^...^x with parentheses inserted in all possible ways is not represented by the sequence A000081? ~~Is it exactly the set of positive algebraic numbers?~~ Is it a superset of positive algebraic numbers? Is it countable? Is $2^{\sqrt 2}$ or $\log_2 3$ in the set?

edited Oct 30 2011 at 3:05

Vladimir Reshetnikov

community wiki

3 revisions

Off-hand, I'd be quite surprised if the generic number isn't attained in the case $x = 3$. Am I missing something? – Todd Trimble Oct 29 2011 at 2:34

1

The case $x=3$ gives oeis.org/A003018 which differs from oeis.org/A000081 starting from 7th term. – Vladimir Reshetnikov Oct 29 2011 at 2:53

2

Wow, that's really surprising! Can you tell me which two parenthesizations in the case $x = 3$ coincide? – Todd Trimble Oct 29 2011 at 3:07

10

3^(3^(3^3) * 3 * 3 * 3) = 3^(3^(3 * 3 * 3) * 3^3). [I've written these using products in the exponent, which of course can be rewritten into iterated exponentiations in various equivalent orders] – Sridhar Ramesh Oct 29 2011 at 5:50

6

The same phenomenon occurs for any natural number, of course: b^(b^(b^b) * the product of b many bs) = b^(b^(the product of b many bs) * b^b). So every natural number b fails to be generic for parenthesization of x^x^x... with 4 + b many copies of x. [Paraphrased from "The Nesting and Roosting Habits of The Laddered Parenthesis", by R. K. Guy and J. L. Selfridge] – Sridhar Ramesh Oct 29 2011 at 5:51

show 1 more comment

Todd Trimble · Accepted Answer · 2011-10-29 03:01:37Z UTC

The answer to the second question is "no". Consider the unique solution $x > 0$ to the equation $x^x = 3$. By the Gelfond-Schneider theorem, this number is transcendental. But we have

$$((x^x)^x)^x = x^{x^3} = x^{(x^{(x^x)})}$$

so that two of the parenthesizations coincide. So evidently this set contains transcendental numbers. Lots of other solutions can be similarly generated (e.g., solve $x^{(x^x)} = 4$).

Number of distinct values taken by x^x^…^x with parentheses inserted in all possible ways

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.