57

Suppose we have a power tower consisting of $2$ occurring $n$ times:

$$\huge2^{2^{2^{.^{.^{.^{2}}}}}}$$

How many values can we generate by placing any number of parenthesis?

It is fairly simple for the first few values of $n$:

  • There is $1$ value for $n=1$:
    • $2=2$
  • There is $1$ value for $n=2$:
    • $4=2^{2}$
  • There is $1$ value for $n=3$:
    • $16=({2^{2})^{2}}=2^{(2^{2})}$
  • There are $2$ values for $n=4$:
    • $256=(({2^{2})^{2}})^2=(2^{(2^{2})})^2=(2^{2})^{(2^{2})}$
    • $65536=2^{(({2^{2})^{2}})}=2^{(2^{(2^{2})})}$

Any idea how to formulate a general solution?

I'm thinking that it might be feasible using a recurrence relation.

Thanks

barak manos
  • 42,695
  • 8
  • 56
  • 133
  • To begin, I have been trying to count how many ways to put the parenthesis there are. No result so far. My approach: in Polish notation, the power tower can be written as a sequence of $n$ twos and $n-1$ power signs ($^\wedge$), such that among the $k$ first symbols there are more twos than powers, for $k$ from $1$ to $2n-1$. – ajotatxe Nov 24 '16 at 11:40
  • @ajotatxe: I think that's plain Fibonacci. The problem is that many different ways yield the same value. I was thinking more in the direction of minimum and maximum values, then simply count all the possible values between them, but I'm not really sure how to calculate those bounds. – barak manos Nov 24 '16 at 11:42
  • 8
    It's a special case of the number of different words of inserting $n$ parentheses in $n+1$ (distinct) letters, hence an upper bound for your number is given by the [Catalan numbers](https://oeis.org/A000108), but the intractability of this particular case lies in that we have to deal with a special case of the mutuabola $2^{(2^2)}=(2^2)^2$, hence you have to count out words which contain this particular grouping and give non-distinct values, thereby lowering the count. –  Nov 24 '16 at 12:27
  • 5
    It's not quite that simple, because, while that gives you $\left(\color{darkred}{{2^{(2^2)}}}\right)^2 = \left(\color{darkred}{{(2^2)}^2}\right)^2$, it does not also give you $\left({(2^2)}^2\right)^2= {(2^2)}^{(2^2)}$. – MJD Nov 28 '16 at 00:05
  • Incidentally, for $n=5$ there are 8 values. – MJD Nov 28 '16 at 00:09
  • 3
    Are you sure that's not $8$ values for $n = 6$? Sloane's could be wrong, though. http://oeis.org/A002845 – Mr. Brooks Nov 28 '16 at 22:08
  • Yes, that's what I meant, thanks. – MJD Nov 30 '16 at 15:11
  • 6
    Aha, OEIS gives a reference to [“The Nesting and Roosting Habits of the Laddered Parenthesis](http://oeis.org/A003018/a003018.pdf) by Guy and Selfridge. – MJD Nov 30 '16 at 15:14
  • 1
    Maybe the question should be asked at http://mathoverflow.net/ – Ernesto Iglesias Feb 08 '17 at 20:59
  • @YiannisGalidakis I just spotted your comment which I have unwittingly repeated in my answer; although I have included a couple of references. The nice image provided by John Baez helps visualise the problem. – it's a hire car baby Apr 28 '17 at 10:41
  • 1
    @MJD Yiannis is correct. The counterexample you give is an example of $2^{(2^2)}=(2^2)^2$, which is essentially a rule that the brackets are transitive in that particular case. If you look at your construct, the transitivity Yiannis describes is present in it, and if you use Yiannis's identity twice you prove your identity. – it's a hire car baby Apr 28 '17 at 10:47
  • 1
    @RobertFrost You are quite right. Thanks for the correction. – MJD Apr 30 '17 at 16:43
  • @barakmanos not sure but does this give you a means to the answer: https://math.stackexchange.com/questions/2274507/ – it's a hire car baby May 10 '17 at 10:05
  • 1
    There are more identities beyond $(x^2)^2 = x^{(2^2)}$. That one is fairly easy to deal with, by prohibiting $(2^2)$ as an exponent. But there are also unrelated identities like ${(2^{( {({(2^2)}^2)}^2 )})}^{( 2^{({(2^2)}^2)} )} = {(2^{( 2^{({(2^2)}^2)} )})}^{( {({(2^2)}^2)}^2 )}$. In general, in any expression of the form $((a^b)^c\ldots)^d$, permuting $\{b,c,\ldots,d\}$ has no effect on the value. The key thing to determine, it seems, is are there any further possible identities? Once this is known, the counting can begin. – Matt May 22 '17 at 09:44
  • 1
    I would start, by thinking about exponent rules. Some of which are: $$(a^b)^c = a^{(b\cdot c)}\\ (a^b)^c\neq a^{(b^c)}$$ It's really more of a question of how many unique products can you make with n-1 two's, and then n-2 two's, etc. you're finding that as you go. –  Jun 27 '17 at 02:19
  • 1
    Along the lines of what @Matt said, I wonder if we can define an "irreducible" identity as one where you can't, by substitution using smaller identities, reduce it to two syntactically equivalent things. My gut tells me there are infinite irreducible identities like the one Matt shows and as we increase $n$ we get more and more, making it harder and harder to count. A recurrence relation would be easy to write in terms of syntax alone, but these identities over the syntax are the essence of what complicates this. – Colm Bhandal Aug 22 '17 at 15:29
  • 1
    @Matt it has been discussed above that your identities are arrived at by the transitivity of brackets in the case of $2^{(2^2)}=(2^2)^2$ – it's a hire car baby Apr 04 '18 at 17:46
  • 1
    @ProducerofBS That would be lovely, but can you prove that? And if so, can you use the proof to count what the OP asks? – Colm Bhandal Apr 05 '18 at 17:13
  • 1
    @ProducerofBS I think you're oversimplifying things, but I can't prove anything and would be gladly proved incorrect :) actually what the OP asks is *this* matter; what you're proposing is a different matter. Perhaps it belongs in a separate question. – Colm Bhandal Apr 06 '18 at 09:33
  • 1
    @ProducerofBS true. I don't mean to be mean or discourage any tangential efforts by the way. Who knows, it might lead to a breakthrough. My intuition just tells me otherwise, but again I'd gladly be proven wrong on this. I have no ideas right now on how to tackle this. – Colm Bhandal Apr 06 '18 at 09:42
  • 1
    @ProducerofBS That's the bit I'm worried about. If you move some brackets to the right, and some to the left, you might strike gold and find another identity. Good luck though ;) If I was you, first thing I'd do is write a computer program to search for counterexamples to your claim: irreducible identities other than the given one that are irreducible. The longer it runs without an answer, the more confident I'd be of your claim. I'd imagine the check for irreducibility would require the most effort in such a program. – Colm Bhandal Apr 06 '18 at 15:52
  • 1
    @ProducerofBS Actually the check for irreducibility wouldn't be too bad. Assuming the algorithm parses the things into abstract syntax trees, $T_1$ and $T_2$, with child trees $A_1, B_1$ for $T_1$ and $A_2, B_2$ for $T_2$, I think you just need to check that $A_1 \neq A_2$ and $B_1 \neq B_2$. I think. And by the way by $\neq$ I think I mean the *value*, not the *syntax*. – Colm Bhandal Apr 06 '18 at 15:58
  • 1
    @ColmBhandal are you familiar with this https://en.wikipedia.org/wiki/Dyck_language and this https://en.wikipedia.org/wiki/Catalan_number and this http://oeis.org/A002845 ? – it's a hire car baby Apr 06 '18 at 16:01
  • 1
    @ProducerofBS Nope, not really. I see you have similar things in your answer. I still have the unshakeable feeling that this is very tricky. There's not much more value I can add at this stage my friend. – Colm Bhandal Apr 06 '18 at 21:27
  • 1
    @ProducerofBS No, my identity is not arrived at by transitivity of brackets, nor was it discussed above. It is arrived at by the permuting process I described. The identity ${({(2^2)}^2)}^2={(2^2)}^{(2^2)}$ of MJD is also not arrived at via applications of "Yiannis's identity" $2^{(2^2)}={(2^2)}^2$, since the right hand side of MJD's identity does not contain any instance of either side of Yiannis's identity, and so cannot be thereby transformed at all. MJD's right hand side _can_ be obtained by the permutation rule applied to the left hand side of the first equation in MJD's comment. – Matt Apr 07 '18 at 20:28
  • 2
    If you are interested in this problem, by far the best comment in this thread of comments is @MJD's reference above to the paper by Guy and Selfridge. That paper addresses exactly the original question posed here, and surpasses all of the reasoning given in all of these comments. – Matt Apr 07 '18 at 20:32
  • 1
    @Matt Thanks; I agree. All the identities above are not arrived at by the identity $(2^2)^2=2^{(2^2)}$. They're arrived at by the identity $(n^2)^2=n^{(2^2)}$. What I'm curious about at the moment is a counterexample to the statement that all are examples of this. – it's a hire car baby Apr 08 '18 at 09:34
  • 1
    $(2^{(((2^2)^2)^2)^2})^{(2^2)^2} = ((((2^2)^2)^2)^{2^{(2^2)^2}})^2$ is irreducible w.r.t. the permutation rule (even after disallowing $n^{2^2}$ so as to incorporate $(n^2)^2 = n^{2^2}$, $((n^2)^x)^2 = (n^x)^{2^2}$, and so on). – Anders Kaseorg Jan 04 '19 at 15:14
  • 1
    I wonder if the problem would be easier considering $3$s instead of $2$s. Do such identities complicate things when using $3$? – Franklin Pezzuti Dyer Oct 30 '19 at 21:22

1 Answers1

2

There's a maths of this symmetry, they're called Dyck Words, which John Baez talks about here with some helpful diagrams. It is the maths which governs the number of ways in which a certain number of sets of brackets can be nested. It is the symmetries of these Dyck words which give rise to the number of different solutions to any given tetration.

The number of Dyck words of length $2n$ (i.e. representing $2n$ sets of nested brackets, is given by the $n$th Catalan number. However that is not to say that is your answer, because in the case of the number $2$ you have the identity $2^4=4^2$ to contend with, so you need to eliminate those identical solutions from your answer.

I conjectured a solution to this with this question here:

Based on $n$ up to $11$, the solutions to this give $1, 1, 1, 2, 3, 3, 4, 6, 8, 10, 13,$ which match https://oeis.org/A017818.

But I later formed the opinion that I missed the mark with that, as it fails to consider permutations of further dyck words either side of any $(n^2)^2=n^{(2^2)}$.

it's a hire car baby
  • 8,731
  • 2
  • 22
  • 55
  • 2
    For tetration there are more-or-less standard notations (e.g. [Knuth-arrows](https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation) $a\uparrow\uparrow b$), but $a\uparrow b$ is *not* one of them. – r.e.s. Apr 28 '17 at 14:12
  • 1
    @r.e.s. Thanks. I wasn't sure how studied a subject it was, although I knew I had seen arrows. I've standardised what I put; pls let me know if wrong. – it's a hire car baby Apr 28 '17 at 15:04