login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A296062 Base-2 logarithm of the number of different shapes of balanced binary trees with n nodes (A110316). 7
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, 0, 5, 8, 11, 12, 15, 16, 17, 16, 19, 20, 21, 20, 21, 20, 19, 16, 19, 20, 21, 20, 21, 20, 19, 16, 17, 16, 15, 12, 11, 8, 5, 0, 6, 10, 14, 16, 20, 22, 24, 24, 28 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

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.

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

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

Also, the minimum Colless index of a rooted bifurcating tree with n leaves. - Francesc Rosselló, Apr 08 2019

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

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..16383 (first 10001 terms from Robert Israel)

Pieter C. Allaart and Kiko Kawamura, The Takagi Function: a Survey, Real Analysis Exchange, pp. 1-54, Vol. 37, No. 1, 2011-12.

T. M. Coronado and F. Rosselló, The minimum value of the Colless index, arXiv:1903.11670 [q-bio.PE], 2019. - Francesc Rosselló, Apr 08 2019

T. M. Coronado et. al, On the minimum value of the Colless index and the bifurcating trees that achieve it, Journal of Mathematical Biology, pp. 1993-2054, Vol. 80, 2020.

M. Kruppel, On the extrema and the improper derivatives of Takagi’s continuous nowhere differentiable function, pp. 41-59, Rostock. Math. Kolloq.,Vol. 62, 2007.

Jeffrey C. Lagarias, The Takagi function and its properties, arXiv:1112.4205 [math.CA], 2011-2012.

Jeffrey C. Lagarias, The Takagi function and its properties, 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.

Wikipedia, Blancmange curve

FORMULA

a(0) = a(1) = 0; a(2*n) = a(n) + a(n-1) + 1; a(2*n+1) = 2*a(n).

a(n) = A007814(A110316(n)).

2^a(n) = A110316(n).

G.f. g(x) satisfies g(x) = (1+x)^2*g(x^2) + x^2/(1-x^2). - Robert Israel, Dec 04 2017

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

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

From Laura Monroe, Oct 23 2020: (Start)

a(n+1) = (2^k)*tau(x/(2^k)), where tau is the Takagi function, and n = (2^k) + x with x < 2^k.

a(n) = n - A268289(n). (End)

MAPLE

a:= proc(n) option remember; local r; `if`(n<2, 0,

      `if`(irem(n, 2, 'r')=0, 1+a(r)+a(r-1), a(r)*2))

    end:

seq(a(n), n=0..100);  # Alois P. Heinz, Dec 04 2017

MATHEMATICA

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 *)

PROG

(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

(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

CROSSREFS

Cf. A007814, A110316, A268289.

Sequence in context: A071442 A124759 A071295 * A214178 A117652 A103223

Adjacent sequences:  A296059 A296060 A296061 * A296063 A296064 A296065

KEYWORD

nonn,look,easy

AUTHOR

Katarzyna Matylla, Dec 04 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 12:03 EDT 2021. Contains 348168 sequences. (Running on oeis4.)