cp's OEIS Frontend

A296062 Base-2 logarithm of the number of different shapes of balanced binary trees with n nodes (A110316).

%I A296062 #93 Mar 09 2024 11:16:32
%S A296062 0,0,1,0,2,2,2,0,3,4,5,4,5,4,3,0,4,6,8,8,10,10,10,8,10,10,10,8,8,6,4,
%T A296062 0,5,8,11,12,15,16,17,16,19,20,21,20,21,20,19,16,19,20,21,20,21,20,19,
%U A296062 16,17,16,15,12,11,8,5,0,6,10,14,16,20,22,24,24,28
%N A296062 Base-2 logarithm of the number of different shapes of balanced binary trees with n nodes (A110316).
%C A296062 Since terms of A110316 are always powers of 2, it seems natural to have a sequence of the exponents too. Also, it conveys the same information as A110316 but is shorter and more readable.
%C A296062 Also, sum of absolute distances from (n+1) to the nearest multiple of 2^k for all 2^k < n+1. - _Ivan Neretin_, Jul 03 2018
%C A296062 Also, the minimum cost of connecting n+1 nodes when the cost of joining two connected components is the absolute difference of their sizes. In particular, connecting two equal sized components has zero cost. For example, in the case of n=4 there are 5 nodes. Connecting nodes 1 and 2 costs zero, connecting nodes 3 and 4 costs zero, then connecting {5} to {3,4} costs 1 and finally connecting {1,2} to {3,4,5} costs 1 giving a total cost of 2. Because this solution is optimal a(4) = 2. - _Qingnian Su_, Nov 03 2018
%C A296062 Also, the minimum Colless index of a rooted bifurcating tree with n leaves. - _Francesc Rosselló_, Apr 08 2019
%C A296062 Also, dilations of the Takagi function restricted to dyadic rationals in [0,1]. The number of points of a(n) in each dilation is 2^k and the scale of each dilation in both the x and y directions is 2^k, where k = floor(log_2(n+1)). See Allaart et. al (2012), Equation 4.7, attributed to Kruppel (2007). Also see Coronado et.al (2020), Corollary 4. - _Laura Monroe_, Oct 23 2020
%D A296062 Hsien-Kuei Hwang, S, Janson, T.-H. Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968, 2022.
%H A296062 Alois P. Heinz, <a href="/A296062/b296062.txt">Table of n, a(n) for n = 0..16383</a> (first 10001 terms from Robert Israel)
%H A296062 Pieter C. Allaart and Kiko Kawamura, <a href="https://www.jstor.org/stable/10.14321/realanalexch.37.1.0001">The Takagi Function: a Survey</a>, Real Analysis Exchange, pp. 1-54, Vol. 37, No. 1, 2011-12.
%H A296062 T. M. Coronado and F. Rosselló, <a href="https://arxiv.org/abs/1903.11670">The minimum value of the Colless index</a>, arXiv:1903.11670 [q-bio.PE], 2019. - _Francesc Rosselló_, Apr 08 2019
%H A296062 T. M. Coronado et. al, <a href="https://doi.org/10.1007/s00285-020-01488-9">On the minimum value of the Colless index and the bifurcating trees that achieve it</a>, Journal of Mathematical Biology, pp. 1993-2054, Vol. 80, 2020.
%H A296062 M. Kruppel, <a href="http://ftp.math.uni-rostock.de/pub/romako/heft62/kru62.pdf">On the extrema and the improper derivatives of Takagi’s continuous nowhere differentiable function</a>, pp. 41-59, Rostock. Math. Kolloq.,Vol. 62, 2007.
%H A296062 Jeffrey C. Lagarias, <a href="https://arxiv.org/abs/1112.4205">The Takagi function and its properties</a>, arXiv:1112.4205 [math.CA], 2011-2012.
%H A296062 Jeffrey C. Lagarias, <a href="http://hdl.handle.net/2433/198081">The Takagi function and its properties</a>, In Functions in number theory and their probabilistic aspects, 153--189, RIMS Kôkyûroku Bessatsu, B34, Res. Inst. Math. Sci. (RIMS), Kyoto, 2012. MR3014845.
%H A296062 Laura Monroe, <a href="https://arxiv.org/abs/2111.05996">A Few Identities of the Takagi Function on Dyadic Rationals</a>, arXiv:2111.05996 [math.CO], 2021.
%H A296062 Laura Monroe, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL27/Monroe/monroe2.pdf">Takagi Function Identities on Dyadic Rationals</a>, J. Int. Seq (2024) Vol. 27, Art. 24.2.7.
%H A296062 Wikipedia, <a href="https://en.wikipedia.org/wiki/Blancmange_curve">Blancmange curve</a>
%F A296062 a(0) = a(1) = 0; a(2*n) = a(n) + a(n-1) + 1; a(2*n+1) = 2*a(n).
%F A296062 a(n) = A007814(A110316(n)).
%F A296062 2^a(n) = A110316(n).
%F A296062 G.f. g(x) satisfies g(x) = (1+x)^2*g(x^2) + x^2/(1-x^2). - _Robert Israel_, Dec 04 2017
%F A296062 a(n) = min_{i=1..floor((n+1)/2)} n + 1 - 2*i + a(i-1) + a(n-i). - _Qingnian Su_ and _Andrew Howroyd_, Nov 04 2018
%F A296062 a(n) = Sum_{j=2..k} (m_1-m_j-2*(j-2))*2^m_j where m_1 > ... > m_k are the exponents in the binary expansion of n. - _Francesc Rosselló_, Apr 08 2019
%F A296062 From _Laura Monroe_, Oct 23 2020: (Start)
%F A296062 a(n+1) = (2^k)*tau(x/(2^k)), where tau is the Takagi function, and n = (2^k) + x with x < 2^k.
%F A296062 a(n) = n - A268289(n). (End)
%p A296062 a:= proc(n) option remember; local r; `if`(n<2, 0,
%p A296062       `if`(irem(n, 2, 'r')=0, 1+a(r)+a(r-1), a(r)*2))
%p A296062     end:
%p A296062 seq(a(n), n=0..100);  # _Alois P. Heinz_, Dec 04 2017
%t A296062 Fold[Append[#1, If[EvenQ@ #2, #1[[#2/2 + 1]] + #1[[#2/2]] + 1, 2 #1[[(#2 - 1)/2 + 1]]]] &, {0, 0}, Range[2, 72]] (* _Michael De Vlieger_, Dec 04 2017 *)
%o A296062 (PARI) seq(n)={my(v=vector(n)); for(m=2, #v, v[m]=vecmin(vector(m\2, i, v[i] + v[m-i] + m-2*i))); v} \\ _Andrew Howroyd_, Nov 04 2018
%o A296062 (PARI) seq(n)={my(v=vector(n)); for(n=1, n-1, v[n+1]=if(n%2, 2*v[(n+1)/2], v[n/2] + v[n/2+1] + 1)); v} \\ _Andrew Howroyd_, Nov 04 2018
%o A296062 (Python)
%o A296062 def A296062(n): return (k:=n+1)-(sum(i.bit_count() for i in range(1,k))<<1)+k*(m:=k.bit_length())-(1<<m) # _Chai Wah Wu_, Mar 02 2023
%Y A296062 Cf. A007814, A110316, A268289.
%K A296062 nonn,look,easy
%O A296062 0,5
%A A296062 _Katarzyna Matylla_, Dec 04 2017