A080776 Oscillating sequence which rises to 2^(k-1) in k-th segment (k>=1) then falls back to 0.
0, 0, 1, 0, 1, 2, 1, 0, 1, 2, 3, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 31, 30
Offset: 0
Keywords
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; http://140.109.74.92/hk/wp-content/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
- R. Stephan, Some divide-and-conquer sequences ...
- R. Stephan, Table of generating functions
Crossrefs
Essentially the same as A053646.
Formula
G.f.: -1 + 2/(1-x) + 1/(1-x)^2 * (-1 + sum(k>=0, 2t^2(t-1), t=x^2^k)). a(n) = A005942(n+2) - 3(n+1), n>0. - Ralf Stephan, Sep 13 2003
a(0)=0, a(2n) = a(n) + a(n-1) + (n==1), a(2n+1) = 2a(n). - Ralf Stephan, Oct 20 2003
Comments