25

I am looking for a reasonably fast algorithm to calculate terms of the OEIS sequence A002845. Let me restate its definition here.

Let ^ denote the exponentiation operator. Consider expressions of the form 2^2^...^2 having n 2's with parentheses inserted in all possible ways (the number of possible parenthesizations is given by Catalan numbers). Some of these expressions will have the same value, for example (2^2)^2=2^(2^2). We are interested in the number of distinct values for a given n.

There is an obvious brute-force solution through a direct calculation of these expressions, but it is clear that the required time and space quickly exceed all reasonable limits even for relatively small n. I'm interested in a polynomial-time solution to this problem.

Vladimir Reshetnikov
  • 11,750
  • 4
  • 30
  • 51
  • 5
    There is a somewhat related question on MO: http://mathoverflow.net/questions/103411/number-of-distinct-values-taken-by-alpha-alpha-dots-alpha-with – Vladimir Reshetnikov Jul 31 '12 at 18:16
  • 3
    Have you read the linked papers? http://www.jstor.org/stable/2316312?seq=1 and http://www.jstor.org/stable/10.2307/2319392. Though I've only glanced at it, the former shows equivalence to some tree-based things that might be helpful. – Danica Jul 31 '12 at 18:17
  • 3
    Another related question on MO: http://mathoverflow.net/questions/79442/ –  Jul 31 '12 at 18:32
  • @Dougal: Yes, I've read those papers. Unfortunately, no algorithm is given there. – Vladimir Reshetnikov Jul 31 '12 at 19:49
  • 1
    @Vladimir: are there any more examples of equal values? I suspect there are no except trivial ones, as 2^2^...^2 is growing very fast with the number of terms (but I cannot prove it). – Vlad Aug 01 '12 at 16:39
  • 4
    @Vlad: (2^2)^(2^2) = ((2^2)^2)^2 – Vladimir Reshetnikov Aug 01 '12 at 21:37
  • The brute-force solution can be sped up via dynamic programming - augment the solution with a hashtable (e.g. {"2^2", 4}; {"2^(2^2)", 16}), so that you don't need to keep recomputing the sub-problems. Have you looked into something like this? – Zim-Zam O'Pootertoot Apr 30 '13 at 20:55
  • 1
    Free copy of the paper (not all of us have jstor) http://oeis.org/A003018/a003018.pdf – Colonel Panic May 03 '13 at 21:01
  • I liked the question, just for curiosity, what is this useful for? – sites May 04 '13 at 03:39

3 Answers3

3

Just represent the numbers in iterated base 2: a Num has a (possibly empty) list of distinct children x1,...,xp of type Num, so that Num([x1,...,xp]) == 2^x1 + ... + 2^xp.

This defines a unique way to write a nonnegative integer; remember to sort the exponents so that comparison makes sense. The equalities:

  • 2^x + 2^x == 2^(x+1) == Num([x+1])
  • 2^x + 2^y == Num([x,y]) when x != y
  • (2^2^x)^2^y == 2^2^(x+y) == Num([Num([x+y])])

along with associativity/commutativity of addition allow you to add arbitrary numbers and compute x^y for numbers of the form 2^2^k; this class of numbers contains 2 (with k=0) and is closed under ^ so this guarantees that every number we need to manipulate is of this form.

Furthermore, the equalities defined above never increase the number of nodes in the tree, so all the Num are of size O(n).

So the time complexity is actually O(C * n^k) which is quasi-linear in C (C is the (n-1)-th Catalan number).

Generic Human
  • 6,027
  • 1
  • 17
  • 10
1

I think the best solution here involves dynamic programming, a difficult concept to grasp, but very efficient if done correctly. The idea is to minimize the number of times you have to do a certain calculation, by remembering the results of calculations you've already done, and then using this knowledge to split the problem into a subset of simpler problems.

For example, in your 2^(2^2) = (2^2)^2 example, we can now remember this as two things that are equivalent to the value of 16. So now when we see this tacked on to 2^(2^(2^2)) = 2^((2^2)^2) we can very quickly identify each of these as 2 ^ 16, do the calculation once, and we now have two new equations to add to the list of values we never have to calculate again.

This may not seem to help much, however, when you end up with very long series of parenthesized questions, with even longer sets of equivalencies, it will save you a of time and complexity, in what are very long calculations for a computer to do on very large numbers. Pseudo code below, I appologize, this is really broad psuedo code, this problem is pretty rough, so I didn't want to write out an entire algorithm. Just really outlined the concept in more detail

 sortedEquivalencyVector;  //Sorted greatest first, so we are more likely to se longest matches

 function(expression)

    if(portion of expression exists)  //Remember, you can only do this from the end of the expression in toward the middle!
         replace value at end of expression that matches with its already computed value

    if(simplified version exists in vector) add original expression to vector
    else compute value and add it to the vector
 end
MobA11y
  • 18,425
  • 3
  • 49
  • 76
  • 2
    Still, even without recalculation, the values would grow extremely fast - it would take enormous time and memory to calculate such a value even once. – Zakharia Stanley May 03 '13 at 16:24
  • Yes, but just because a problem is hard does not mean that it is avoidable... the idea is to limit the number of long calculations to a minimum. If you have an answer that avoids doing them completely why don't you provide it. – MobA11y May 03 '13 at 16:30
  • 3
    I do not have an answer, and I do not claim I have. But your post is not an answer either. You just gave some obvious recommendations that were already given in a comment to the question, and they do not help with the main obstacle to the solution - huge numbers. Nothing personal, but I just think this question is very interesting and deserves a real answer. – Zakharia Stanley May 03 '13 at 17:50
  • I actually completely disagree. The question isn't directed at computing the value of 2^2^2^2^2^2, but it directed at the complexity of computing it for all of the combinations of parentheses. One is an algorithmic problem directed at stack overlflow, the other is a mathematical problem, which isn't what the question was about "I'm interested in a polynomial-time solution to this problem." suggesting he is more concered about the big-oh complexity of the overall solution, than he is about simplifying one of the calculations of one instance. – MobA11y May 03 '13 at 18:23
  • I guess, overall, mine is the best solution on this board. It doesn't necessarily deserve to be "accepted" if it is too computationally complex to be implemented, but it is still theoretically correct and doesn't deserve the down vote. – MobA11y May 03 '13 at 18:37
  • 1
    Useful thoughts, but unfortunately, not an answer. It could not be used to directly calculate the sequence in question. – Oksana Gimmel May 04 '13 at 15:04
0

One approach which is much better than brute-force (but admittedly still expensive) is to use the concept of "standard form" in the first linked paper. Given an n, generate each standard form of degree n, evaluate it, and keep all values in a set. At the end, check the size of the set.

The grammar for a standard form is 

S -> (2 ^ P)
P -> (S * P)
P -> S
S -> 2

You start with an S, and at the end you should have n terminals (i.e. 2s).

mitchus
  • 4,677
  • 3
  • 35
  • 70