This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A277267 #71 May 15 2022 23:50:44
%S A277267 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,
%T A277267 15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,16,17,18,19,20,21,22,
%U A277267 23,24,25,26,27,28,29,30,31,31,31,31,31,31,31,31,31
%N A277267 Minimum number of single-direction edges in leveled binary trees with n nodes.
%C A277267 A leveled binary tree is a binary tree where every level, except possibly the last, is completely filled.
%C A277267 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 A277267 The formula for obtaining this integer series counts the minimum 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 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.
%H A277267 George Tanev, <a href="/A277267/b277267.txt">Table of n, a(n) for n = 1..10000</a>
%H A277267 Stevo Bozinovski, 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 A277267 NIST, <a href="https://xlinux.nist.gov/dads/HTML/heightBalancedTree.html">Height-balanced tree</a>
%H A277267 NIST, <a href="https://xlinux.nist.gov/dads/HTML/completeBinaryTree.html">Complete-binary tree</a>
%H A277267 NIST, <a href="https://xlinux.nist.gov/dads/HTML/fullBinaryTree.html">Full-binary tree</a>
%F A277267 a(n) = 2^(h-1) - 1 + (n - 3*2^(h-1) + 1) * H(n - 3*2^(h-1) + 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).
%F A277267 Proof:
%F A277267 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 sub-node, 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.
%F A277267 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 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 left.
%F A277267 2) The last level of the leveled binary tree can contain at most 2^h nodes. If it is filled with right sub-nodes first, the number of left edges will not increase, up to a point when all of the right sub-nodes have been inserted and the next node to be inserted will have to be a left sub-node. As is evident in the given examples, it is possible to insert only right sub-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 sub-node must be inserted in the last level (h = 2), since there is no more room to insert right sub-nodes. 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^(h-1), 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^(h-1) - 1. Therefore, the number of strictly left edges will increase only when 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 H(n - 3*2^(h-1) + 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^(h-1) + 1.
%F A277267 The sum of the terms in sections (1) and (2) leads to the final formula: a(n) = 2^(h-1) - 1 + (n - 3*2^(h-1) + 1)*H(n - 3*2^(h-1) + 1).
%F A277267 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
%F A277267 a(n) = n - 1 - A279521(n). - _Alois P. Heinz_, Nov 16 2020
%e A277267 In a leveled binary tree with 1 node, there are at least 0 strictly left edges: n=1 => a(n)=0.
%e A277267 o
%e A277267 In a leveled binary tree with 2 nodes, there are at least 0 strictly left edges: n=2 => a(n)=0.
%e A277267 o
%e A277267 \
%e A277267 o
%e A277267 In a leveled binary tree with 3 nodes, there is at least 1 strictly left edge: n=3 => a(n)=1.
%e A277267 o
%e A277267 => / \
%e A277267 o o
%e A277267 In a leveled binary tree with 4 nodes, there is at least 1 strictly left edge: n=4 => a(n)=1.
%e A277267 o
%e A277267 => / \
%e A277267 o o
%e A277267 \
%e A277267 o
%e A277267 In a leveled binary tree with 5 nodes, there is at least 1 strictly left edge: n=5 => a(n)=1.
%e A277267 o
%e A277267 => / \
%e A277267 o o
%e A277267 \ \
%e A277267 o o
%e A277267 In a leveled binary tree with 6 nodes, there are at least 2 strictly left edges: n=6 => a(n)=2.
%e A277267 ___o
%e A277267 => / \
%e A277267 o o
%e A277267 => / \ \
%e A277267 o o o
%e A277267 In a leveled binary tree with 7 nodes, there are at least 3 strictly left edges: n=7 => a(n)=3.
%e A277267 ___o___
%e A277267 => / \
%e A277267 o o
%e A277267 => / \ => / \
%e A277267 o o o o
%e A277267 In a leveled binary tree with 8 nodes, there are at least 3 strictly left edges: n=8 => a(n)=3.
%e A277267 ___o___
%e A277267 => / \
%e A277267 __o o
%e A277267 => / \ => / \
%e A277267 o o o o
%e A277267 \
%e A277267 o
%e A277267 In a leveled binary tree with 9 nodes, there are at least 3 strictly left edges: n=9 => a(n)=3.
%e A277267 _____o___
%e A277267 => / \
%e A277267 __o o
%e A277267 => / \ => / \
%e A277267 o o o o
%e A277267 \ \
%e A277267 o o
%e A277267 And so on.
%e A277267 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 + ...
%p A277267 a:= n-> (b-> max(n-b, b/2-1))(2^ilog2(n)):
%p A277267 seq(a(n), n=1..100); # _Alois P. Heinz_, Dec 20 2016
%t A277267 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 *)
%o A277267 (Java)
%o A277267 static int a(int n) {
%o A277267 double h = Math.floor(Math.log(n) / Math.log(2));
%o A277267 double k = Math.pow(2, h - 1);
%o A277267 return (int) (k - 1 + (n - 3*k + 1) * Heaviside(n - 3*k + 1));
%o A277267 }
%o A277267 static int Heaviside(double x) {
%o A277267 return x>=0 ? 1 : 0;
%o A277267 } // _George Tanev_, Oct 07 2016
%o A277267 (PARI) a(n)=my(h=logint(n,2),k=2^(h-1),t=n - 3*k + 1);return(k-1+if(t>=0,t,0)); \\ _Joerg Arndt_, Oct 11 2016
%Y A277267 Cf. A056971, A279521.
%K A277267 nonn
%O A277267 1,6
%A A277267 _Adrijan Božinovski_ and _George Tanev_, Oct 07 2016