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 A279521 #91 Jun 24 2024 11:31:11
%S A279521 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 A279521 15,15,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,31,31,31,31,
%U A279521 31,31,31,31,31,31,31,31,31,31,31,31,32,33,34,35,36,37,38
%N A279521 Maximum number of single-direction edges in leveled binary trees with n nodes.
%C A279521 A leveled binary tree is a binary tree where every level, except possibly the last, is completely filled.
%C A279521 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 A279521 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 A279521 This sequence also gives the number of different nonordered neighboring pairs in the Stern-Brocot sequence A002487. - _Horst H. Manninger_, Jun 10 2021
%C A279521 Number of nodes in the left subheap of a binary heap of length n. - _Alois P. Heinz_, Jun 24 2024
%H A279521 Adrijan Božinovski, <a href="/A279521/b279521.txt">Table of n, a(n) for n = 1..10000</a>
%H A279521 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 A279521 NIST, <a href="https://xlinux.nist.gov/dads/HTML/heightBalancedTree.html">Height-balanced tree</a>
%H A279521 NIST, <a href="https://xlinux.nist.gov/dads/HTML/completeBinaryTree.html">Complete binary tree</a>
%H A279521 NIST, <a href="https://xlinux.nist.gov/dads/HTML/fullBinaryTree.html">Full binary tree</a>
%F A279521 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 A279521 Proof:
%F A279521 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 A279521 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 A279521 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 A279521 There are two cases to consider:
%F A279521 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 A279521 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 A279521 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 A279521 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 A279521 a(n) = n - 1 - A277267(n). - _Alois P. Heinz_, Nov 16 2020
%F A279521 a(n) = A006165(n+1) - 1. - _Alois P. Heinz_, Feb 03 2024
%e A279521 In a leveled binary tree with 1 node, there are at most 0 strictly right edges: n=1 => a(n)=0.
%e A279521 . o
%e A279521 In a leveled binary tree with 2 nodes, there are at most 1 strictly right edges: n=2 => a(n)=1.
%e A279521 . o
%e A279521 . \ <=
%e A279521 . o
%e A279521 In a leveled binary tree with 3 nodes, there are at most 1 strictly right edges: n=3 => a(n)=1.
%e A279521 . o
%e A279521 . / \ <=
%e A279521 . o o
%e A279521 In a leveled binary tree with 4 nodes, there are at most 2 strictly right edges: n=4 => a(n)=2.
%e A279521 . o
%e A279521 . / \ <=
%e A279521 . o o
%e A279521 . \ <=
%e A279521 . o
%e A279521 In a leveled binary tree with 5 nodes, there are at most 3 strictly right edges: n=5 => a(n)=3.
%e A279521 . o___
%e A279521 . / \ <=
%e A279521 . o o
%e A279521 . \ <= \ <=
%e A279521 . o o
%e A279521 In a leveled binary tree with 6 nodes, there are at most 3 strictly right edges: n=6 => a(n)=3.
%e A279521 . ___o___
%e A279521 . / \ <=
%e A279521 . o o
%e A279521 . / \ <= \ <=
%e A279521 . o o o
%e A279521 In a leveled binary tree with 7 nodes, there are at most 3 strictly right edges: n=7 => a(n)=3.
%e A279521 . ___o___
%e A279521 . / \ <=
%e A279521 . o o
%e A279521 . / \ <= / \ <=
%e A279521 . o o o o
%e A279521 In a leveled binary tree with 8 nodes, there are at most 4 strictly right edges: n=8 => a(n)=4.
%e A279521 . ___o___
%e A279521 . / \ <=
%e A279521 . __o o
%e A279521 . / \ <= / \ <=
%e A279521 . o o o o
%e A279521 . \ <=
%e A279521 . o
%e A279521 In a leveled binary tree with 9 nodes, there are at most 5 strictly right edges: n=9 => a(n)=5.
%e A279521 . ___o___
%e A279521 . / \ <=
%e A279521 . __o o
%e A279521 . / \ <= / \ <=
%e A279521 . o o o o
%e A279521 . \ <= \ <=
%e A279521 . o o
%e A279521 And so on.
%p A279521 a:= n-> (g-> min(g-1, n-g/2))(2^ilog2(n)):
%p A279521 seq(a(n), n=1..100); # _Alois P. Heinz_, Nov 16 2020
%t A279521 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 A279521 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 A279521 For[g = 2, g < m, g++, AppendTo[lis, Length[Sort[DeleteDuplicates[Sort[#] & /@ (Partition[t[[1 ;; g]], 2, 1])]]]]]
%t A279521 lis (* _Horst H. Manninger_, Jun 10 2021 *)
%o A279521 (Java)
%o A279521 static int a(int n)
%o A279521 {
%o A279521 int h = (int) Math.floor(Math.log(n) / Math.log(2));
%o A279521 int p2h = (int) Math.pow(2, h);
%o A279521 int p2h_1 = (int) Math.pow(2, h-1);
%o A279521 int He = Heaviside(-n + 3*p2h_1 - 1);
%o A279521 return (int) ((n + p2h_1 - 1)*He + Math.pow(-1, He)*(p2h - 1));
%o A279521 }
%o A279521 static int Heaviside(double x)
%o A279521 {
%o A279521 return x >= 0 ? 1 : 0;
%o A279521 }
%o A279521 (Scala)
%o A279521 def a(n: Int): Int = {
%o A279521 val h = Math.floor(Math.log(n) / Math.log(2)).toInt
%o A279521 val p2h = Math.pow(2, h).toInt
%o A279521 val p2h_1 = Math.pow(2, h - 1).toInt
%o A279521 val hs = heaviside(-n + 3 * p2h_1 - 1)
%o A279521 ((n + p2h_1 - 1) * hs + Math.pow(-1, hs) * (p2h - 1)).toInt
%o A279521 }
%o A279521 /** _George Tanev_, Jan 01 2017 */
%o A279521 def heaviside(x: Double): Int = if (x >= 0) 1 else 0
%o A279521 (Python)
%o A279521 class A279521():
%o A279521 @staticmethod
%o A279521 def _heaviside(x):
%o A279521 return 1 if x >= 0 else 0
%o A279521 @staticmethod
%o A279521 def at(n):
%o A279521 h = n.bit_length() -1
%o A279521 p2h = 2**h
%o A279521 p2h_1 = 2**(h-1)
%o A279521 hs = A279521._heaviside(-n + 3 * p2h_1 - 1)
%o A279521 return ((n + p2h_1 - 1) * hs + (-1)**hs * (p2h - 1))
%o A279521 print([A279521.at(n) for n in range(1,100)])
%o A279521 # _George Tanev_, Jan 01 2017, indentation _R. J. Mathar_, Mar 29 2023
%Y A279521 Cf. A002487, A006165, A056971, A277267, A002487.
%Y A279521 Essentially partial sums of A086694.
%K A279521 nonn
%O A279521 1,4
%A A279521 _Adrijan Božinovski_, Dec 14 2016