Date: Fri, 19 Jan 2001 14:08:20 +0100 (MET) From: Jonas Wallgren Remarks on Hierarchical Sequences The starting point for sequences A059126 on is sequence A001511: 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,... (Every 2nd element is 1, every 4th element is 2, every 8th element is 3, ...) I'll call that sequence W1. It could be described as consisting of phrases - in the musical sense: 1,2,1 is a short phrase. I'll say that its height is 2. A longer phrase is 1,2,1,3,1,2,1 with height=3. The new sequence (A059126) is 1,2,1,3,4,3,1,2,1,5,6,5,1,2,1,3,4,3,1,2,1,... Using brackets it could be written as (1,2,1),(3,4,3),(1,2,1),(5,6,5),(1,2,1),(3,4,3),(1,2,1),... All elements in this (bracketed) sequence are height-2-phrases. Every 2nd element is 1,2,1, every 4th element is 3,4,3, etc. Thus it's a nesting of phrases, some kind of 2-level structure. The second element begins with 3 because that's the first number not used before (in the first element). I'll call this sequence W2{2} - the first "2" is the nesting, the second "2" is the height of the elements. Next sequence in this set is A059127 (in its bracketed form): (1,2,1,3,1,2,1),(4,5,4,6,4,5,4),(1,2,1,3,1,2,1),... which is W2{3} since the elements are height-3-phrases. Next sequence (bracketed) is A059128: ((1,2,1),(3,4,3),(1,2,1)),((5,6,5),(7,8,7),(5,6,5)),((1,2,1),(3,4,3),(1,2,1)),.. . This sequence uses two levels of nesting. It's W3{2,2} since its elements are height-2-phrases whose elements are height-2-phrases. (W1 is not nested - one level. W2 has one level of nesting - giving 2 levels. W3 has two levels of nesting - giving 3 levels.) Next sequence is A059129: (1,2,1),(2,3,2),(1,2,1),(3,4,3),(1,2,1),(2,3,2),(1,2,1),... It's quite close to W2{2}, but now the second element begins with 2 because that's the first number not *beginning* an (the first) element. It's notated W2{2}* More sequences are A059130, notated W2{3}*, and A059131, notated W3{2,2}*. They have the same structures as W2{3} and W3{2,2}, but they contain somewhat smaller integers. Now, there are a couple of ways to "reduce" these sequences, to combine their elements: · If x and y are sequences then y=S(x) means that y[n]=the sum of the first 2^n-1 elements of x. (2^n-1 is the length of a phrase.) (It is used only when x isn't nested.) · If X is the notation of a sequence then Xc is the notation of the "collapsed" sequence, i.e. the result of replacing the innermost phrases by the sums of their elements. E.g.: ((1,2,1),(3,4,3)) gives (4,10) An already existing sequence is A000295, which in this notation is S(W1). Some more sequences in the same vein: W2{2}c : A059132 S(W2{2}c) : A059133 W2{3} : A059134 S(W2{3}) : A059135 W3{2,2}c : A059136 W3{2,2}cc : A059137 S(W3{2,2}cc} : A059138 W2{2}*c : A059139 S(W2{2}*c) : A059140 W2{3}*c : A059141 S(W2{3}*) : A059142 W3{2,2}*c : A059143 W3{2,2}*cc : A059144 S(W3{2,2}*cc): A059145 Since there is something very "power-of-2-ish" about this (e.g. the phrase lengths of 2^n-1) one could use A006519 as a starting point instead of A001511. (A006519: 1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,16, ...) All sequences with notations not using S or c now will contain consecutive powers of 2 instead of consecutive integers. The notation for these sequences uses W' instead of W.) Some W' sequences are: W'1 : A006519 W'2{2} : A059146 W'2{3} : A059147 W'3{2,2} : A059148 W'2{2}* : A059149 W'2{3}* : A059150 W'3{2,2}* : A059151 S(W'1) : A001787 W'2{2}c : A059152 S(W'2{2}c) : A059153 W'2{3}c : A059154 S(W'2{3}c) : A059155 W'3{2,2}c : A059156 W'3{2,2}cc : A059157 S(W'3{2,2}cc) : A059158 W'2{2}*c : A059159 S(W'2{2}*c) : A058922 W'2{3}*c : A059161 S(W'2{3}*c) : A059162 W'3{2,2}*c : A059163 W'3{2,2}*cc : A059164 S(W'3{2,2}*cc): A059165 ------------ Jonas W