OFFSET
0,3
COMMENTS
The value of a(n) is always a power of 2.
REFERENCES
Hsien-Kuei Hwang, S Janson, TH Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016; https://algo.stat.sinica.edu.tw/hk/files/2016/12/aat-hhrr-1.pdf. Also Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..2047
Jeffrey A. Barnett, Counting Balanced Tree Shapes
Ann Wells Clifton, Structural and Computational Results on Equitably Dissectible Graphs, Ph. D. Dissertation, Louisiana Tech. (2025). See p. 76.
Samuele Giraudo, Intervals of balanced binary trees in the Tamari lattice, arXiv preprint arXiv:1107.3472 [math.CO], 2011.
Wikipedia, Blancmange curve
FORMULA
a(0) = a(1) = 1; a(2*n) = 2*a(n)*a(n-1); a(2*n+1) = a(n)*a(n).
a(n) = 1 <=> n in { A000225 }. - Orson R. L. Peters, Mar 12 2024
MAPLE
a:= proc(n) option remember; local r; `if`(n<2, 1,
`if`(irem(n, 2, 'r')=0, 2*a(r)*a(r-1), a(r)^2))
end:
seq(a(n), n=0..50); # Alois P. Heinz, Apr 10 2013
MATHEMATICA
a[0] = a[1] = 1; a[n_] := a[n] = If[EvenQ[n], 2 a[n/2] a[n/2-1], a[(n-1)/2 ]^2]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jan 31 2016 *)
PROG
(Python)
def A110316(n): return 1<<(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
CROSSREFS
KEYWORD
AUTHOR
Jeffrey Barnett, Jun 23 2007
STATUS
approved
