A005536 a(0) = 0; thereafter a(2n) = n - a(n) - a(n-1), a(2n+1) = n - 2a(n) + 1.
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
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
Programs
-
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 *) -
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
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
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.
Comments