|
|
A002845
|
|
Number of distinct values taken by 2^2^...^2 (with n 2's and parentheses inserted in all possible ways).
(Formerly M1139 N0435)
|
|
24
|
|
|
1, 1, 1, 2, 4, 8, 17, 36, 78, 171, 379, 851, 1928, 4396, 10087, 23273, 53948, 125608, 293543, 688366, 1619087, 3818818, 9029719, 21400706, 50828664, 120963298, 288405081, 688821573, 1647853491, 3948189131, 9473431479
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
|
|
REFERENCES
|
J. Q. Longyear, personal communication.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
R. K. Guy, Letter to N. J. A. Sloane, June 24 1971: front, back [Annotated scanned copy, with permission]
|
|
EXAMPLE
|
The table with explicit lists of values starts as follows:
n | distinct values of 2^...^2 with all possible parenthesizations
-----+---------------------------------------------------------------
1 | 2
2 | 2^2 = 4
3 | (2^2)^2 = 2^(2^2) = 16
4 | (2^2^2)^2 = 2^8 = 256, (2^2)^(2^2) = 2^(2^2^2) = 2^16 (= 65536)
5 | 256^2 = 2^16, (2^16)^2 = 2^32, 2^256, 2^2^16 (~ 2*10^19728)
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
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,
| 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
...| ...
(When parentheses are omitted above, we use that ^ is right associative.) (End)
|
|
PROG
|
(PARI) /* Define operators for numbers represented (recursively) as list of positions of bits 1. Illustration using the commands below: T = 3.bits; T.int */
n.bits = vector(hammingweight(n), v, n -= 1 << v= valuation(n, 2); v.bits)
ONE = 1.bits; m.int = sum(i=1, #m, 1<<m[i].int) /* Convert back. (Not needed.) */
{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
{MUL(m, n)= my(S=[]); #n && foreach(m, b, S=ADD(S, [ADD(c, b)| c<-n])); S}
{RSHIFT(m, n=ONE)= if(!#m|| !#n|| !(#m[1]|| #m=m[^1]), m, [SUB(b, n)| b<-m, CMP(b, n)>=0])}
{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)}
{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))}
{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)}
A2845 = List([[2.bits]]) /* List of values for each n */
{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]}
\\ Unoptimized code, for illustration. Slow for n >= 15. - M. F. Hasler, Apr 28 2024
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,more,changed
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|