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