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.