A005536 - OEIS

%I M2274 #67 Jul 19 2024 08:48:26

%S 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,

%T 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,

%U 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

%N a(0) = 0; thereafter a(2n) = n - a(n) - a(n-1), a(2n+1) = n - 2a(n) + 1.

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

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

%D 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.

%H T. D. Noe, <a href="/A005536/b005536.txt">Table of n, a(n) for n = 0..10000</a>

%H J.-P. Allouche and J. Shallit, <a href="https://doi.org/10.1016/S0304-3975(03)00090-2">The Ring of k-regular Sequences, II</a>, Theoret. Computer Sci., 307 (2003), 3-29.

%H Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint 2016.

%H Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="https://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.

%H Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, p. 44 and 49.

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F 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

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

%F 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

%t 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 *)

%o (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

%o (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)

%o (Python)

%o from sympy.ntheory import digits

%o 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

%Y Cf. A071992, A073059.

%K nonn,look

%O 0,6

%A _N. J. A. Sloane_

%E More terms and better description from _Ralf Stephan_, Sep 13 2003

%E a(0)=0 added to data and offset changed by _N. J. A. Sloane_, Jun 16 2021 at the suggestion of _Georg Fischer_.