A082499 Take a string of n x's and insert n-1 ^'s and n-2 pairs of parentheses in all possible legal ways. Sequence gives number of distinct values when x = sqrt(2).

1, 1, 2, 4, 8, 17, 38, 88, 206, 497, 1212, 2996

Offset: 1

Author

W. Edwin Clark and Wouter Meeussen, Apr 29 2003

Keywords

• nonn
• more

Comments

For n=10, largest value is 2^(2^127) = x^(x^(x^(x^(x^6)))) = x^(x^(x^((((((x^x)^x)^x)^x)^x)^x))) and results from the 132nd tree {0,{0,{0,{{{{{{0,0},0},0},0},0},0}}}} or {1,0,1,0,1,0,1,1,1,1,1,1,0,0,0,0,0,0}.

Examples

			For n = 4 there are 5 functions: f1(x) = ((x^x)^x)^x; f2(x) = (x^(x^x))^x; f3(x) = x^((x^x)^x); f4(x) = x^(x^(x^x)); f5(x) = (x^x)^(x^x); but only 4 different values when x = sqrt(2).
		

Links

• F. Goebel and R. P. Nederpelt, The number of numerical outcomes of iterated powers, Amer. Math. Monthly, 80 (1971), 1097-1103.
• R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis, Amer. Math. Monthly 80 (8) (1973), 868-876.
• R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis (annotated cached copy)
• Index entries for sequences related to parenthesizing

Crossrefs

Cf. A003019, A000081, A002845, A003018, A082543.

Programs

Mathematica

trees[1] = {x};
trees[n_] := trees[n] = Flatten@Table[ch1^ch2, {k, n-1}, {ch1, trees[k]}, {ch2, trees[n-k]}];
logs[t_] := ((log/@t) //. {log[a_^b_]:>log[a]b, log[a_ b_]:>log[a]+log[b], log[x]->one, log[one]->0});
Table[Length@Union[logs@logs@trees[n] /. {one->1, x->Sqrt[2]}, SameTest->Equal], {n, 9}] (* Andrei Zabolotskii, Jan 03 2025 *)

Extensions

Term a(11) = 1212 added by Vladimir Reshetnikov, Oct 29 2011

a(1) added by Franklin T. Adams-Watters, Nov 03 2011

a(12) from Andrei Zabolotskii, Jul 23 2025