[seqfan] binary tree sequences
Jeremy Gardiner
jeremy.gardiner at btinternet.com
Sat Oct 15 21:22:47 CEST 2011
Consider an infinite complete binary tree with root node labelled 1 and
child nodes at each fork labelled 0 and 1.
Then a path from the root to any node in the tree corresponds to a (finite)
increasing sequence of (binary representations of) positive integers and
every positive integer corresponds to a unique node in the tree.
Now define a sequence A(n) in terms of some arbitrary binary sequence B(n)
by a(0) = 1, a(n+1) = 2*a(n) + b(n+1) for n >= 0.
Note that A(n) and B(n) have the same parity for n > 0.
I call such a sequence A(n) a binary tree sequence since A(n) corresponds to
some path through the binary tree just described.
Binary tree sequences have the following properties:
Any such A(n) is a "superincreasing" sequence where each term is greater
than the sum of all the preceding terms (see
http://en.wikipedia.org/wiki/Superincreasing_sequence)
Given some term a(n) for n > 0 we can find a(n-1) by removing the least
significant bit of the binary representation of a(n) ("right shift").
All the binary tree sequences are 'squeezed' between 2^n = 1,2,4,8,16, ...
and 2^(n+1)-1 = 1,3,7,15,31, ... in the sense that a(n) >= 2^n and a(n) <=
2^(n+1)-1 for n >= 0.
The first few terms of a binary tree sequence can only be one of the
following:
1,2,4,8,16,
1,2,4,8,17,
1,2,4,9,18,
1,2,4,9,19,
1,2,5,10,20,
1,2,5,10,21,
1,2,5,11,22,
1,2,5,11,23,
1,3,6,12,24,
1,3,6,12,25,
1,3,6,13,26,
1,3,6,13,27,
1,3,7,14,28,
1,3,7,14,29,
1,3,7,15,30,
1,3,7,15,31,
The OEIS contains several examples of binary tree sequences including
A000079(n), A000225(n+1) and A000975(n+1).
I wonder if binary tree sequences are sufficiently interesting, perhaps to
be worth an index entry in the OEIS?
Are these sequences already known by another name?
Jeremy Gardiner
More information about the SeqFan
mailing list