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,6

Comments

k-th segment has length 2^k (k>=0).

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

Table of n, a(n) for n=0..97.

R. Stephan, Some divide-and-conquer sequences ...

R. Stephan, Table of generating functions

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

Crossrefs

Essentially the same as A053646.

Sequence in context: A004074 A245615 A053646 * A376813 A360659 A297158

Adjacent sequences: A080773 A080774 A080775 * A080777 A080778 A080779

Keyword

nonn

Author

N. J. A. Sloane, Mar 11 2003

Status

approved