|
%I #125 Feb 22 2024 09:05:38
%S 0,0,0,1,0,0,1,2,0,0,0,1,1,1,2,3,0,0,0,1,0,0,1,2,1,1,1,2,2,2,3,4,0,0,
%T 0,1,0,0,1,2,0,0,0,1,1,1,2,3,1,1,1,2,1,1,2,3,2,2,2,3,3,3,4,5,0,0,0,1,
%U 0,0,1,2,0,0,0,1,1,1,2,3,0,0,0,1,0,0,1,2,1,1,1,2,2,2,3,4,1,1,1,2,1,1,2,3,1
%N a(n) is the number of occurrences of '11' in the binary expansion of n.
%C a(n) takes the value k for the first time at n = 2^(k+1)-1. Cf. A000225. - _Robert G. Wilson v_, Apr 02 2009
%C a(n) = A213629(n,3) for n > 2. - _Reinhard Zumkeller_, Jun 17 2012
%H Reinhard Zumkeller, <a href="/A014081/b014081.txt">Table of n, a(n) for n = 0..10000</a>
%H J.-P. Allouche, <a href="http://math.colgate.edu/~integers/graham2/graham2.Abstract.html">On an Inequality in a 1970 Paper of R. L. Graham</a>, INTEGERS 21A (2021), #A2.
%H Jean-Paul Allouche and Jeffrey Shallit, <a href="https://doi.org/10.1007/BFb0097122">Sums of digits and the Hurwitz zeta function</a>, in: K. Nagasaka and E. Fouvry (eds.), Analytic Number Theory, Lecture Notes in Mathematics, Vol. 1434, Springer, Berlin, Heidelberg, 1990, pp. 19-30.
%H John Brillhart and L. Carlitz, <a href="https://doi.org/10.1090/S0002-9939-1970-0260955-6">Note on the Shapiro Polynomials</a>, Proceedings of the American Mathematical Society, volume 25, number 1, May 1970, pages 114-118 (see A001782 for a scanned copy), with a(n) = exponent in theorem 4.
%H Helmut Prodinger, <a href="http://dx.doi.org/10.1137/0603004">Generalizing the sum of digits function</a>, SIAM J. Algebraic Discrete Methods, Vol. 3, No. 1 (1982), pp. 35-42. MR0644955 (83f:10009). [See B_2(11,n) on p. 35. - _N. J. A. Sloane_, Apr 06 2014]
%H Michel Rigo and Manon Stipulanti, <a href="https://arxiv.org/abs/2103.16966">Revisiting regular sequences in light of rational base numeration systems</a>, arXiv:2103.16966 [cs.FL], 2021. Mentions this sequence.
%H Bartosz Sobolewski and Lukas Spiegelhofer, <a href="https://arxiv.org/abs/2309.00142">Block occurrences in the binary expansion</a>, arXiv:2309.00142 [math.NT], 2023.
%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences with (relatively) simple ordinary generating functions</a>, 2004.
%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DigitBlock.html">Digit Block</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Rudin-ShapiroSequence.html">Rudin-Shapiro Sequence</a>.
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F a(4n) = a(4n+1) = a(n), a(4n+2) = a(2n+1), a(4n+3) = a(2n+1) + 1. - _Ralf Stephan_, Aug 21 2003
%F G.f.: (1/(1-x)) * Sum_{k>=0} t^3/((1+t)*(1+t^2)), where t = x^(2^k). - _Ralf Stephan_, Sep 10 2003
%F a(n) = A000120(n) - A069010(n). - _Ralf Stephan_, Sep 10 2003
%F Sum_{n>=1} A014081(n)/(n*(n+1)) = A100046 (Allouche and Shallit, 1990). - _Amiram Eldar_, Jun 01 2021
%e The binary expansion of 15 is 1111, which contains three occurrences of 11, so a(15)=3.
%p # To count occurrences of 11..1 (k times) in binary expansion of v:
%p cn := proc(v, k) local n, s, nn, i, j, som, kk;
%p som := 0;
%p kk := convert(cat(seq(1, j = 1 .. k)),string);
%p n := convert(v, binary);
%p s := convert(n, string);
%p nn := length(s);
%p for i to nn - k + 1 do
%p if substring(s, i .. i + k - 1) = kk then som := som + 1 fi od;
%p som; end; # This program no longer worked. Corrected by _N. J. A. Sloane_, Apr 06 2014.
%p [seq(cn(n,2),n=0..300)];
%p # Alternative:
%p A014081 := proc(n) option remember;
%p if n mod 4 <= 1 then procname(floor(n/4))
%p elif n mod 4 = 2 then procname(n/2)
%p else 1 + procname((n-1)/2)
%p fi
%p end proc:
%p A014081(0):= 0:
%p map(A014081, [$0..1000]); # _Robert Israel_, Sep 04 2015
%t f[n_] := Count[ Partition[ IntegerDigits[n, 2], 2, 1], {1, 1}]; Table[ f@n, {n, 0, 104}] (* _Robert G. Wilson v_, Apr 02 2009 *)
%t Table[SequenceCount[IntegerDigits[n,2],{1,1},Overlaps->True],{n,0,120}] (* _Harvey P. Dale_, Jun 06 2022 *)
%o (Haskell)
%o import Data.Bits ((.&.))
%o a014081 n = a000120 (n .&. div n 2) -- _Reinhard Zumkeller_, Jan 23 2012
%o (PARI) A014081(n)=sum(i=0,#binary(n)-2,bitand(n>>i,3)==3) \\ _M. F. Hasler_, Jun 06 2012
%o (PARI) a(n) = hammingweight(bitand(n, n>>1)) ;
%o vector(105, i, a(i-1)) \\ _Gheorghe Coserea_, Aug 30 2015
%o (Python)
%o def a(n): return sum([((n>>i)&3==3) for i in range(len(bin(n)[2:]) - 1)]) # _Indranil Ghosh_, Jun 03 2017
%o (Python)
%o from re import split
%o def A014081(n): return sum(len(d)-1 for d in split('0+', bin(n)[2:]) if d != '') # _Chai Wah Wu_, Feb 04 2022
%Y Cf. A014082, A033264, A037800, A056973, A000225, A213629, A000120, A069010, A100046.
%Y First differences give A245194.
%Y A245195 gives 2^a(n).
%K nonn,base,easy
%O 0,8
%A _Simon Plouffe_
|
