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

Links

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

Hsien-Kuei Hwang, S. Janson, and T.-H. 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.

Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, 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.

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

Ralf 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

a(n) = A053646(n+1). - M. F. Hasler, Oct 27 2025

Prog

(PARI) apply( {A080776(n, e=exponent(n++))=min(n-2^e, 2<<e-n)}, [0..99]) \\ M. F. Hasler, Oct 27 2025
(Python)
def A080776(n): return min(n+1-(m:=1<<(n+1).bit_length()-1), (m<<1)-n-1) # Chai Wah Wu, Oct 31 2025

Crossrefs

Up to the offset the same as A053646.

Sequence in context: A245615 A391928 A053646 * A376813 A360659 A297158

Adjacent sequences: A080773 A080774 A080775 * A080777 A080778 A080779

Keyword

nonn

Author

N. J. A. Sloane, Mar 11 2003

Status

approved