

A277267


Minimum number of singledirection edges in leveled binary trees with n nodes.


2



0, 0, 1, 1, 1, 2, 3, 3, 3, 3, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 9, 10, 11, 12, 13, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,6


COMMENTS

A leveled binary tree is a binary tree where every level, except possibly the last, is completely filled.
Unlike a complete binary tree, where nodes in the last level are always stacked linearly from left to right, insertion in a leveled binary tree can be done in any order.
The formula for obtaining this integer series counts the minimum number of singledirection edges in a leveled binary tree of an arbitrary size n, and is presented alongside its proof. The same formula gives the minimum number of right, as well as the minimum number of left, edges in any leveled binary tree. The proof is analogous for both cases.


LINKS

George Tanev, Table of n, a(n) for n = 1..10000
Stevo Bozinovski, Adrijan Bozinovski, Brain Rhythms, Pascal Triangle, and BrainComputer Interface, ICEST (Ohrid, North Macedonia 2019), 191193.
NIST, Heightbalanced tree
NIST, Completebinary tree
NIST, Fullbinary tree


FORMULA

a(n) = 2^(h1)  1 + (n  3*2^(h1) + 1) * H(n  3*2^(h1) + 1), where h = log_2(n) and is the height of the binary tree, and H is the Heaviside function (i.e., H(x) = 1 if x >= 0 and H(x) = 0 if x < 0).
Proof:
If n = 2^k  1 (for any k > 0), i.e., if n = {3, 7, 15, ...}, the binary tree is full, and, as any tree, contains n1 edges (1 fewer than the number of nodes). Any n = 2^k  1 is an odd number, so the number one less than that is always even. In a full binary tree, every internal (i.e., nonleaf) node has both a left and a right subnode, so there will be equally as many left as right edges in such a tree. Thus, half of that number will be the number of strictly left or strictly right edges. In this proof, strictly left edges will be viewed (the proof is analogous for strictly right edges). The proof will treat both terms in the addition in separate sections.
1) If n != 2^k  1, the leveled binary tree is not full. More precisely, the last level (level h) isn't full, but the subtree consisting of the root and all the levels of the tree up to (and including) level h1 is. As in one of the examples, the leveled tree with n = 8 is not full and has a height of h = 3, but its subtree up to and including level h = 2 is full. 2^h  1 nodes will form the full subtree, which will have 2^h  2 edges, and half of those edges, i.e., 2^(h1)  1, will be strictly left.
2) The last level of the leveled binary tree can contain at most 2^h nodes. If it is filled with right subnodes first, the number of left edges will not increase, up to a point when all of the right subnodes have been inserted and the next node to be inserted will have to be a left subnode. As is evident in the given examples, it is possible to insert only right subnodes in the last level of the leveled binary trees with n = 4 and n = 5, but in a leveled binary tree with n = 6 a left subnode must be inserted in the last level (h = 2), since there is no more room to insert right subnodes. This forces an increase in the number of left edges. It can be observed that the moment when the number of left edges in a leveled binary tree must increase is when a node is entered after half of the possible positions to insert nodes in the last level, i.e., 2^h / 2 = 2^(h1), have been occupied. Furthermore, the number of nodes in the leveled binary tree must be greater than the sum of the nodes already present in the previous levels of the tree and half of the nodes in the last level, in order for the minimum number of left edges to increase; otherwise the minimum number of left edges will remain 2^(h1)  1. Therefore, the number of strictly left edges will increase only when n > 2^h  1 + 2^(h1), i.e., n > 3*2^(h1)  1, or, stated differently, n  3*2^(h1) + 1 > 0. This condition can be expressed with the Heaviside step function as H(n  3*2^(h1) + 1), and the minimum number of left edges will increase by the difference between the total number of nodes and the number of nodes already present, which is n  3*2^(h1) + 1.
The sum of the terms in sections (1) and (2) leads to the final formula: a(n) = 2^(h1)  1 + (n  3*2^(h1) + 1)*H(n  3*2^(h1) + 1).
Also a(n) = sum(b2(i),i=1..n), where b2(i) is the 2nd significant bit in the binary expansion of i.  Jeffrey Shallit, May 09 2019
a(n) = n  1  A279521(n).  Alois P. Heinz, Nov 16 2020


EXAMPLE

In a leveled binary tree with 1 node, there are at least 0 strictly left edges: n=1 => a(n)=0.
o
In a leveled binary tree with 2 nodes, there are at least 0 strictly left edges: n=2 => a(n)=0.
o
\
o
In a leveled binary tree with 3 nodes, there is at least 1 strictly left edge: n=3 => a(n)=1.
o
=> / \
o o
In a leveled binary tree with 4 nodes, there is at least 1 strictly left edge: n=4 => a(n)=1.
o
=> / \
o o
\
o
In a leveled binary tree with 5 nodes, there is at least 1 strictly left edge: n=5 => a(n)=1.
o
=> / \
o o
\ \
o o
In a leveled binary tree with 6 nodes, there are at least 2 strictly left edges: n=6 => a(n)=2.
___o
=> / \
o o
=> / \ \
o o o
In a leveled binary tree with 7 nodes, there are at least 3 strictly left edges: n=7 => a(n)=3.
___o___
=> / \
o o
=> / \ => / \
o o o o
In a leveled binary tree with 8 nodes, there are at least 3 strictly left edges: n=8 => a(n)=3.
___o___
=> / \
__o o
=> / \ => / \
o o o o
\
o
In a leveled binary tree with 9 nodes, there are at least 3 strictly left edges: n=9 => a(n)=3.
_____o___
=> / \
__o o
=> / \ => / \
o o o o
\ \
o o
And so on.
G.f. = x^3 + x^4 + x^5 + 2*x^6 + 3*x^7 + 3*x^8 + 3*x^9 + 3*x^10 + 3*x^11 + 4*x^12 + ...


MAPLE

a:= n> (b> max(nb, b/21))(2^ilog2(n)):
seq(a(n), n=1..100); # Alois P. Heinz, Dec 20 2016


MATHEMATICA

Table[Function[h, 2^(h  1)  1 + Boole[# >= 0] # &@ (n  3*2^(h  1) + 1)]@ Floor[Log2@ n], {n, 71}] (* Michael De Vlieger, Oct 12 2016 *)


PROG

(Java)
static int a(int n) {
double h = Math.floor(Math.log(n) / Math.log(2));
double k = Math.pow(2, h  1);
return (int) (k  1 + (n  3*k + 1) * Heaviside(n  3*k + 1));
}
static int Heaviside(double x) {
return x>=0 ? 1 : 0;
} // George Tanev, Oct 07 2016
(PARI) a(n)=my(h=logint(n, 2), k=2^(h1), t=n  3*k + 1); return(k1+if(t>=0, t, 0)); \\ Joerg Arndt, Oct 11 2016


CROSSREFS

Cf. A056971, A279521.
Sequence in context: A025782 A120506 A327041 * A246262 A275974 A052288
Adjacent sequences: A277264 A277265 A277266 * A277268 A277269 A277270


KEYWORD

nonn


AUTHOR

Adrijan Božinovski and George Tanev, Oct 07 2016


STATUS

approved



