A014081 a(n) is the number of occurrences of '11' in the binary expansion of n.
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, 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, 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
Offset: 0
Examples
The binary expansion of 15 is 1111, which contains three occurrences of 11, so a(15)=3.
Links
- Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
- J.-P. Allouche, On an Inequality in a 1970 Paper of R. L. Graham, INTEGERS 21A (2021), #A2.
- Jean-Paul Allouche and Jeffrey Shallit, Sums of digits and the Hurwitz zeta function, in: K. Nagasaka and E. Fouvry (eds.), Analytic Number Theory, Lecture Notes in Mathematics, Vol. 1434, Springer, Berlin, Heidelberg, 1990, pp. 19-30.
- John Brillhart and L. Carlitz, Note on the Shapiro Polynomials, 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.
- Helmut Prodinger, Generalizing the sum of digits function, 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]
- Michel Rigo and Manon Stipulanti, Revisiting regular sequences in light of rational base numeration systems, arXiv:2103.16966 [cs.FL], 2021. Mentions this sequence.
- Bartosz Sobolewski and Lukas Spiegelhofer, Block occurrences in the binary expansion, arXiv:2309.00142 [math.NT], 2023.
- Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
- Ralf Stephan, Table of generating functions.
- Eric Weisstein's World of Mathematics, Digit Block.
- Eric Weisstein's World of Mathematics, Rudin-Shapiro Sequence.
- Index entries for sequences related to binary expansion of n
Crossrefs
Programs
-
Haskell
import Data.Bits ((.&.)) a014081 n = a000120 (n .&. div n 2) -- Reinhard Zumkeller, Jan 23 2012
-
Maple
# To count occurrences of 11..1 (k times) in binary expansion of v: cn := proc(v, k) local n, s, nn, i, j, som, kk; som := 0; kk := convert(cat(seq(1, j = 1 .. k)),string); n := convert(v, binary); s := convert(n, string); nn := length(s); for i to nn - k + 1 do if substring(s, i .. i + k - 1) = kk then som := som + 1 fi od; som; end; # This program no longer worked. Corrected by N. J. A. Sloane, Apr 06 2014. [seq(cn(n,2),n=0..300)]; # Alternative: A014081 := proc(n) option remember; if n mod 4 <= 1 then procname(floor(n/4)) elif n mod 4 = 2 then procname(n/2) else 1 + procname((n-1)/2) fi end proc: A014081(0):= 0: map(A014081, [$0..1000]); # Robert Israel, Sep 04 2015
-
Mathematica
f[n_] := Count[ Partition[ IntegerDigits[n, 2], 2, 1], {1, 1}]; Table[ f@n, {n, 0, 104}] (* Robert G. Wilson v, Apr 02 2009 *) Table[SequenceCount[IntegerDigits[n,2],{1,1},Overlaps->True],{n,0,120}] (* Harvey P. Dale, Jun 06 2022 *) -
PARI
A014081(n)=sum(i=0,#binary(n)-2,bitand(n>>i,3)==3) \\ M. F. Hasler, Jun 06 2012
-
PARI
a(n) = hammingweight(bitand(n, n>>1)) ; vector(105, i, a(i-1)) \\ Gheorghe Coserea, Aug 30 2015
-
Python
def a(n): return sum([((n>>i)&3==3) for i in range(len(bin(n)[2:]) - 1)]) # Indranil Ghosh, Jun 03 2017
-
Python
from re import split def A014081(n): return sum(len(d)-1 for d in split('0+', bin(n)[2:]) if d != '') # Chai Wah Wu, Feb 04 2022
Formula
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
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
Comments