|
%I M2274 #63 Oct 27 2022 13:25:43
%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)
%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_.
|
