19
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ Off-hand, I'd be quite surprised if the generic number isn't attained in the case $x = 3$. Am I missing something? $\endgroup$
    – Todd Trimble
    Oct 29, 2011 at 2:34
  • 2
    $\begingroup$ The case $x=3$ gives oeis.org/A003018 which differs from oeis.org/A000081 starting from 7th term. $\endgroup$ Oct 29, 2011 at 2:53
  • 2
    $\begingroup$ Wow, that's really surprising! Can you tell me which two parenthesizations in the case $x = 3$ coincide? $\endgroup$
    – Todd Trimble
    Oct 29, 2011 at 3:07
  • 11
    $\begingroup$ 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] $\endgroup$ Oct 29, 2011 at 5:50
  • 6
    $\begingroup$ 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] $\endgroup$ Oct 29, 2011 at 5:51

1 Answer 1

16
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ A similar example I find interesting is to take the unique positive solution of $x^x=x+1$. Then you can easily check that $x^{(x^{(x^x)})} =(x^x)^{(x^x)}$ using the defining equation and the usual exponentiation rules. Although the transcendentality doesn't seem obvious anymore ... $\endgroup$
    – Dejan Govc
    Nov 2, 2011 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.