A005536 a(0) = 0; thereafter a(2n) = n - a(n) - a(n-1), a(2n+1) = n - 2a(n) + 1. (Formerly M2274)

0, 1, 0, 0, 1, 3, 3, 4, 3, 3, 1, 0, 0, 1, 0, 0, 1, 3, 3, 4, 6, 9, 10, 12, 12, 13, 12, 12, 13, 15, 15, 16, 15, 15, 13, 12, 12, 13, 12, 12, 10, 9, 6, 4, 3, 3, 1, 0, 0, 1, 0, 0, 1, 3, 3, 4, 3, 3, 1, 0, 0, 1, 0, 0, 1, 3, 3, 4, 6, 9, 10, 12, 12, 13, 12, 12, 13, 15, 15, 16, 18, 21, 22, 24, 27, 31, 33

Offset

0,6

Comments

A "Von Koch" sequence generated by the first Feigenbaum symbolic sequence.

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. G. Stanton, W. L. Kocay and P. H. Dirksen, Computation of a combinatorial function, pp. 569-578 of C. J. Nash-Williams and J. Sheehan, editors, Proceedings of the Fifth British Combinatorial Conference 1975. Utilitas Math., Winnipeg, 1976.

Links

T. D. Noe, Table of n, a(n) for n = 0..10000

J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.

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.

Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 44 and 49.

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

Ralf Stephan, Table of generating functions

Index entries for sequences related to binary expansion of n

Formula

Partial sums of A065359. a(n) = Sum_{i=0..n} Sum_{k=0..i} (-1)^k*(floor(i/2^k) - 2*floor(i/2^(k+1))). - Benoit Cloitre, Mar 28 2004

G.f.: (1/(1-x)^2) * Sum_{k>=0} (-1)^k*x^2^k/(1 + x^2^k). - Ralf Stephan, Apr 27 2003

a(n) = -n*(n-2) + 3*Sum_{k=1..n-1} Sum_{i=1..k} A035263(i+1), where A035263 is the first Feigenbaum symbolic sequence. - Benoit Cloitre, May 29 2003

Mathematica

a[n_] := a[n] = If[n == 0, 0, hn = Floor[n/2]; If[OddQ[n], hn - 2 a[hn] + 1, hn - a[hn] - a[hn - 1]]]; t = Table[a[n], {n, 0, 100}] (* T. D. Noe, Mar 22 2012 *)

Prog

(PARI) a(n)=-n*(n-2)+3*sum(k=1, n-1, sum(i=1, k, abs(subst(Pol(binary(i+1))- Pol(binary(i)), x, 1)%2))) \\ Benoit Cloitre, May 29 2003
(PARI) a(n)=polcoeff(1/(1-x)^2*sum(k=0, 10, (-1)^k*x^2^k/(1+x^2^k)) +O(x^(n+1)), n)
(Python)
from sympy.ntheory import digits
def A005536(n): return sum(sum((0, 1, -1, 0)[i] for i in digits(m, 4)[1:]) for m in range(n+1)) # Chai Wah Wu, Jul 19 2024

Crossrefs

Cf. A071992, A073059.

Sequence in context: A239207 A329157 A082978 * A172515 A188590 A080038

Adjacent sequences: A005533 A005534 A005535 * A005537 A005538 A005539

Keyword

nonn,look

Author

N. J. A. Sloane

Extensions

More terms and better description from Ralf Stephan, Sep 13 2003

a(0)=0 added to data and offset changed by N. J. A. Sloane, Jun 16 2021 at the suggestion of Georg Fischer.

Status

approved