|
%I #89 Feb 03 2024 19:03:34
%S 0,1,1,2,3,3,3,4,5,6,7,7,7,7,7,8,9,10,11,12,13,14,15,15,15,15,15,15,
%T 15,15,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,31,31,31,31,
%U 31,31,31,31,31,31,31,31,31,31,31,31,32,33,34,35,36,37,38
%N Maximum number of single-direction edges in leveled binary trees with n nodes.
%C A leveled binary tree is a binary tree where every level, except possibly the last, is completely filled.
%C 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.
%C The formula for this integer sequence determines the maximum number of single-direction edges in a leveled binary tree of an arbitrary size n, and is presented alongside its proof. The same formula gives the maximum number of right, as well as the maximum number of left, edges in any leveled binary tree. The proof is analogous for both cases.
%C This sequence also gives the number of different nonordered neighboring pairs in the Stern-Brocot sequence A002487. - _Horst H. Manninger_, Jun 10 2021
%H Adrijan Božinovski, <a href="/A279521/b279521.txt">Table of n, a(n) for n = 1..10000</a>
%H Stevo Bozinovski and Adrijan Bozinovski, <a href="http://rcvt.tu-sofia.bg/ICEST2019_48.pdf">Brain Rhythms, Pascal Triangle, and Brain-Computer Interface</a>, ICEST (Ohrid, North Macedonia 2019), 191-193.
%H NIST, <a href="https://xlinux.nist.gov/dads/HTML/heightBalancedTree.html">Height-balanced tree</a>
%H NIST, <a href="https://xlinux.nist.gov/dads/HTML/completeBinaryTree.html">Complete binary tree</a>
%H NIST, <a href="https://xlinux.nist.gov/dads/HTML/fullBinaryTree.html">Full binary tree</a>
%F a(n) = (n + 2^(h-1) - 1)*He + (-1)^He * (2^h - 1), where h = floor(log_2(n)) and is the height of the binary tree, He = H(-n + 3*2^(h-1) - 1) and H is the Heaviside step function (i.e., H(x) = 1 if x >= 0 and H(x) = 0 if x < 0).
%F Proof:
%F 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 n-1 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., non-leaf) node has both a left and a right child node, so there will be equally as many right as left edges in such a tree. Thus, half of that number will be the number of strictly right or strictly left edges. In this proof, strictly right edges will be viewed (the proof is analogous for strictly left edges).
%F 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 h-1 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^(h-1) - 1, will be strictly right.
%F The last level of the leveled binary tree can contain at most 2^h nodes. If it is filled with right child nodes first, the number of right edges will increase, up to a point when all of the right child nodes have been inserted and the next node to be inserted will have to be a left child node. As is evident in the given examples, it is possible to insert right child nodes 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 child node must be inserted in the last level (h = 2), since there is no more room to insert right child nodes. This forces a stop in the increase of the number of right edges. It can be observed that the moment when the number of right edges in a leveled binary tree must stop increasing 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^(h-1), have been occupied. The number of nodes in the leveled binary tree must be smaller than the number of nodes already present in the previous levels of the tree plus half of the nodes in the last level, in order for the maximum number of right edges to increase; otherwise the maximum number of right edges will remain 2^(h-1) - 1. Therefore, the number of strictly right edges will keep increasing until n < 2^h - 1 + 2^(h-1), i.e., n < 3*2^(h-1) - 1, or, stated differently, -n + 3*2^(h-1) - 1 > 0. This condition can be expressed with the Heaviside step function as He = H(-n + 3*2^(h-1) - 1).
%F There are two cases to consider:
%F 1) When half of the nodes of the last level of the binary tree have been entered (i.e., it holds that He = H(-n + 3*2^(h-1) - 1) = 0), the number of right edges reaches the maximum and it remains constant until the next level starts being filled. This maximum number is 2^h - 1, i.e., the number of strictly right edges of a leveled binary tree of level h+1.
%F 2) While the condition He = H(-n + 3*2^(h-1) - 1) = 1 (i.e., is true), it is possible to insert right child nodes in the last level of the binary tree, thus there are less than half of the possible 2^h nodes in the last level inserted. Since the number of edges in a tree is always one less than the number of nodes, and since the number of nodes in the full binary tree of level h-1 (the level before the last in the leveled binary tree) is 2^(h-1) - 1, the number of edges in the leveled binary tree of level h will be n - 1 - (2^(h-1) - 1) = n - 2^(h-1), as long as He = 1. Since the leveled tree will be filled with right child nodes (and thus right edges) first, n - 2^(h-1) will be the number of strictly right edges in a leveled binary tree of level h while half of the possible right child nodes in the last level have not been completely filled.
%F Therefore, the formula will be 2^h - 1 for He = 0 and n - 2^(h-1) for He = 1. The case for He = 1 can be expressed as n - 2^(h-1) = n + 2^(h-1) - 2^h = n + 2^(h-1) - 1 - 2^h + 1 = n + 2^(h-1) - 1 - (2^h - 1), meaning that the case for He = 1 contains the case for He = 0. Both cases can be represented with a single expression as (n + 2^(h-1) - 1)*He + (-1)^He * (2^h - 1), which is the formula for a(n).
%F For k > 0 we have: a(2k) = 1 + a(k-1) + a(k); a(2k+1) = 1 + 2*a(k). - _Orson R. L. Peters_, Aug 09 2019
%F a(n) = n - 1 - A277267(n). - _Alois P. Heinz_, Nov 16 2020
%F a(n) = A006165(n+1) - 1. - _Alois P. Heinz_, Feb 03 2024
%e In a leveled binary tree with 1 node, there are at most 0 strictly right edges: n=1 => a(n)=0.
%e . o
%e In a leveled binary tree with 2 nodes, there are at most 1 strictly right edges: n=2 => a(n)=1.
%e . o
%e . \ <=
%e . o
%e In a leveled binary tree with 3 nodes, there are at most 1 strictly right edges: n=3 => a(n)=1.
%e . o
%e . / \ <=
%e . o o
%e In a leveled binary tree with 4 nodes, there are at most 2 strictly right edges: n=4 => a(n)=2.
%e . o
%e . / \ <=
%e . o o
%e . \ <=
%e . o
%e In a leveled binary tree with 5 nodes, there are at most 3 strictly right edges: n=5 => a(n)=3.
%e . o___
%e . / \ <=
%e . o o
%e . \ <= \ <=
%e . o o
%e In a leveled binary tree with 6 nodes, there are at most 3 strictly right edges: n=6 => a(n)=3.
%e . ___o___
%e . / \ <=
%e . o o
%e . / \ <= \ <=
%e . o o o
%e In a leveled binary tree with 7 nodes, there are at most 3 strictly right edges: n=7 => a(n)=3.
%e . ___o___
%e . / \ <=
%e . o o
%e . / \ <= / \ <=
%e . o o o o
%e In a leveled binary tree with 8 nodes, there are at most 4 strictly right edges: n=8 => a(n)=4.
%e . ___o___
%e . / \ <=
%e . __o o
%e . / \ <= / \ <=
%e . o o o o
%e . \ <=
%e . o
%e In a leveled binary tree with 9 nodes, there are at most 5 strictly right edges: n=9 => a(n)=5.
%e . ___o___
%e . / \ <=
%e . __o o
%e . / \ <= / \ <=
%e . o o o o
%e . \ <= \ <=
%e . o o
%e And so on.
%p a:= n-> (g-> min(g-1, n-g/2))(2^ilog2(n)):
%p seq(a(n), n=1..100); # _Alois P. Heinz_, Nov 16 2020
%t Table[Function[h, n + 2^(h - 1) - 1 * Boole[# >= 0] # &@ (-n + 3*2^(h-1) - 1) + (-1) ^ Boole[# >= 0] # &@ (-n + 3*2^(h-1) - 1) * (2^h - 1)]@ Floor[Log2@ n], {n, 71}] (* _George Tanev_, Jan 01 2017 *)
%t a[0] = 0; a[1] = 1; lis = {}; m = 70;t = Flatten[Table[{a[2*n] = a[n], a[2*n + 1] = a[n] + a[n + 1]}, {n, m}]];
%t For[g = 2, g < m, g++, AppendTo[lis, Length[Sort[DeleteDuplicates[Sort[#] & /@ (Partition[t[[1 ;; g]], 2, 1])]]]]]
%t lis (* _Horst H. Manninger_, Jun 10 2021 *)
%o (Java)
%o static int a(int n)
%o {
%o int h = (int) Math.floor(Math.log(n) / Math.log(2));
%o int p2h = (int) Math.pow(2, h);
%o int p2h_1 = (int) Math.pow(2, h-1);
%o int He = Heaviside(-n + 3*p2h_1 - 1);
%o return (int) ((n + p2h_1 - 1)*He + Math.pow(-1, He)*(p2h - 1));
%o }
%o static int Heaviside(double x)
%o {
%o return x >= 0 ? 1 : 0;
%o }
%o (Scala)
%o def a(n: Int): Int = {
%o val h = Math.floor(Math.log(n) / Math.log(2)).toInt
%o val p2h = Math.pow(2, h).toInt
%o val p2h_1 = Math.pow(2, h - 1).toInt
%o val hs = heaviside(-n + 3 * p2h_1 - 1)
%o ((n + p2h_1 - 1) * hs + Math.pow(-1, hs) * (p2h - 1)).toInt
%o }
%o /** _George Tanev_, Jan 01 2017 */
%o def heaviside(x: Double): Int = if (x >= 0) 1 else 0
%o (Python)
%o class A279521():
%o @staticmethod
%o def _heaviside(x):
%o return 1 if x >= 0 else 0
%o @staticmethod
%o def at(n):
%o h = n.bit_length() -1
%o p2h = 2**h
%o p2h_1 = 2**(h-1)
%o hs = A279521._heaviside(-n + 3 * p2h_1 - 1)
%o return ((n + p2h_1 - 1) * hs + (-1)**hs * (p2h - 1))
%o print([A279521.at(n) for n in range(1,100)])
%o # _George Tanev_, Jan 01 2017, indentation _R. J. Mathar_, Mar 29 2023
%Y Cf. A002487, A006165, A056971, A277267, A002487.
%Y Essentially partial sums of A086694.
%K nonn
%O 1,4
%A _Adrijan Božinovski_, Dec 14 2016
|
