%I M1139 N0435 #87 Apr 28 2024 21:55:39
%S 1,1,1,2,4,8,17,36,78,171,379,851,1928,4396,10087,23273,53948,125608,
%T 293543,688366,1619087,3818818,9029719,21400706,50828664,120963298,
%U 288405081,688821573,1647853491,3948189131,9473431479
%N Number of distinct values taken by 2^2^...^2 (with n 2's and parentheses inserted in all possible ways).
%C a(n) <= A002955(n). - _Max Alekseyev_, Sep 23 2009
%D J. Q. Longyear, personal communication.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H F. Goebel and R. P. Nederpelt, <a href="http://www.jstor.org/stable/2316312">The number of numerical outcomes of iterated powers</a>, Amer. Math. Monthly, 80 (1971), 1097-1103.
%H R. K. Guy, Letter to N. J. A. Sloane, June 24 1971: <a href="/A002572/a002572.jpg">front</a>, <a href="/A002572/a002572_1.jpg">back</a> [Annotated scanned copy, with permission]
%H R. K. Guy and J. L. Selfridge, <a href="http://www.jstor.org/stable/2319392">The nesting and roosting habits of the laddered parenthesis</a>, Amer. Math. Monthly 80 (8) (1973), 868-876.
%H R. K. Guy and J. L. Selfridge, <a href="/A003018/a003018.pdf">The nesting and roosting habits of the laddered parenthesis</a> (annotated cached copy, with permission)
%H Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a002/A002845.java">Java program</a> (github).
%H J. Longyear, T. Trotter, and N. J. A. Sloane, <a href="/A005321/a005321_2.pdf">Correspondence</a>.
%H MathOverflow, <a href="http://mathoverflow.net/questions/79442/number-of-distinct-values-taken-by-xx-x-with-parentheses-inserted-in-all-pos">MathOverflow discussion of related questions</a>.
%H Vladimir Reshetnikov, <a href="https://github.com/VladimirReshetnikov/Oeis.A002845">Computes terms of OEIS sequence A002845 (C# library)</a>.
%H Jon E. Schoenfield, <a href="/A002845/a002845.txt">The 851 values for n=12</a>.
%H <a href="/index/Par#parens">Index entries for sequences related to parenthesizing</a>
%e From _M. F. Hasler_, Apr 17 2024: (Start)
%e The table with explicit lists of values starts as follows:
%e n | distinct values of 2^...^2 with all possible parenthesizations
%e -----+---------------------------------------------------------------
%e 1 | 2
%e 2 | 2^2 = 4
%e 3 | (2^2)^2 = 2^(2^2) = 16
%e 4 | (2^2^2)^2 = 2^8 = 256, (2^2)^(2^2) = 2^(2^2^2) = 2^16 (= 65536)
%e 5 | 256^2 = 2^16, (2^16)^2 = 2^32, 2^256, 2^2^16 (~ 2*10^19728)
%e 6 | (2^16)^2 = 2^32, 2^64, 2^512, 2^2^16, 2^2^17, 2^2^32, 2^2^256, 2^2^2^16
%e 7 | 2^64, 2^128, 2^256, 2^1024, 2^2^17, 2^2^18, 2^2^32, 2^2^33, 2^2^64, 2^2^257,
%e | 2^2^512, 2^2^2^16, 2^2^65537, 2^2^2^17, 2^2^2^32, 2^2^2^256, 2^2^2^2^16
%e ...| ...
%e (When parentheses are omitted above, we use that ^ is right associative.) (End)
%o (PARI) /* Define operators for numbers represented (recursively) as list of positions of bits 1. Illustration using the commands below: T = 3.bits; T.int */
%o n.bits = vector(hammingweight(n), v, n -= 1 << v= valuation(n, 2); v.bits)
%o ONE = 1.bits; m.int = sum(i=1, #m, 1<<m[i].int) /* Convert back. (Not needed.) */
%o {POW(m,n)= if(#m==1, [MUL(m[1], n)], my(p=ONE); until(!#n || !#m=MUL(m,m), #n[1] || p=MUL(p, m); n=RSHIFT(n)); p)}\\ binary exponentiation unless only 1 bit set
%o {MUL(m,n)= my(S=[]); #n && foreach(m, b, S=ADD(S, [ADD(c, b)| c<-n])); S}
%o {RSHIFT(m, n=ONE)= if(!#m|| !#n|| !(#m[1]|| #m=m[^1]), m, [SUB(b, n)| b<-m, CMP(b, n)>=0])}
%o {ADD(m, n, a=#m, b=#n)= if(!a, n, !b, m, a=b=1; until(a>#m|| b>#n, if(m[a]==n[b], until(a>=#m|| m[a]!=m[a+1]|| !#m=m[^a], m[a]=ADD(m[a],ONE)); b++, CMP(m[a], n[b])<0, a++, m=concat([m[1..a-1], [n[b]], m[a..#m]]); b++)); b>#n|| m=concat(m,n[b..#n]); m)}
%o {CMP(m, n, a=#m, b=#n, c=0)= if(!b, a, !a, -1, while(!(c=CMP(m[a], n[b]))&& a--&& b--, ); if(c, c, 1-b))}
%o {SUB(m, n, a=#n)= if(!a, m, my(b=a=1, c, i); while(a<=#m && b<=#n, if(0>c=CMP(m[a], n[b]), a++, c, i=[c=n[b]]; b++; while(m[a]!=c=ADD(c, ONE), if(b<=#n && c==n[b], b++, i=concat(i, [c]))); m=concat([m[1..a-1], i, m[a+1..#m]]); a += #i, m=m[^a]; b++)); m)}
%o A2845 = List([[2.bits]]) /* List of values for each n */
%o {A002845(n)= while(#A2845<n, my(S=[], n=#A2845); for(k=1, n, foreach(A2845[n-k+1], b, S=setunion(S, Set([POW(a,b)| a<-A2845[k]])))); listput(A2845,S)); #A2845[n]}
%o \\ Unoptimized code, for illustration. Slow for n >= 15. - _M. F. Hasler_, Apr 28 2024
%Y Cf. A003018, A003019, A145545, A145546, A145547, A145548, A145549, A145550, A000081.
%K nonn,nice,more,changed
%O 1,4
%A _N. J. A. Sloane_
%E a(12)-a(13) corrected and a(14)-a(27) added by _Jon E. Schoenfield_, Oct 11 2008
%E a(28)-a(29) computed by Kirill Osenkov, added by _Vladimir Reshetnikov_, Feb 07 2019
%E a(30)-a(31) added by _Sean A. Irvine_, Feb 18 2019
|