A001782 -id:A001782 - cp's OEIS frontend

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

Simon Plouffe

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

a(n) = A213629(n,3) for n > 2. - Reinhard Zumkeller, Jun 17 2012

			The binary expansion of 15 is 1111, which contains three occurrences of 11, so a(15)=3.

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

Cf. A014082, A033264, A037800, A056973, A000225, A213629, A000120, A069010, A100046.
First differences give A245194.
A245195 gives 2^a(n).

import Data.Bits ((.&.))
a014081 n = a000120 (n .&. div n 2)  -- Reinhard Zumkeller, Jan 23 2012

# 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

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

A014081(n)=sum(i=0,#binary(n)-2,bitand(n>>i,3)==3)  \\ M. F. Hasler, Jun 06 2012

a(n) = hammingweight(bitand(n, n>>1)) ;
vector(105, i, a(i-1))  \\ Gheorghe Coserea, Aug 30 2015

def a(n): return sum([((n>>i)&3==3) for i in range(len(bin(n)[2:]) - 1)]) # Indranil Ghosh, Jun 03 2017

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

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
a(n) = A000120(n) - A069010(n). - Ralf Stephan, Sep 10 2003
Sum_{n>=1} A014081(n)/(n*(n+1)) = A100046 (Allouche and Shallit, 1990). - Amiram Eldar, Jun 01 2021

A167167 A001045 with a(0) replaced by -1.

Original entry on oeis.org

-1, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763, 349525, 699051, 1398101, 2796203, 5592405, 11184811, 22369621, 44739243, 89478485, 178956971, 357913941, 715827883, 1431655765, 2863311531

Offset: 0

Paul Curtz, Oct 29 2009

Essentially the same as A001045, and perhaps also A152046.

Also the binomial transform of the sequence with terms (-1)^(n+1)*A128209(n).

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,2).

Concatenation([-1], List([1..35], n-> (2^n -(-1)^n)/3) ); # G. C. Greubel, Dec 01 2019

[-1] cat [(2^n -(-1)^n)/3 : n in [1..35]]; // G. C. Greubel, Dec 01 2019

seq( `if`(n=0, -1, (2^n -(-1)^n)/3), n=0..35); # G. C. Greubel, Dec 01 2019

CoefficientList[Series[(2*x-1+2*x^2)/((1+x)*(1-2*x)), {x, 0, 35}], x] (* G. C. Greubel, Jun 04 2016 *)
Table[If[n==0, -1, (2^n -(-1)^n)/3], {n,0,35}] (* G. C. Greubel, Dec 01 2019 *)
LinearRecurrence[{1,2},{-1,1,1},40] (* Harvey P. Dale, Jul 23 2025 *)

vector(36, n, if(n==1, -1, (2^(n-1) +(-1)^n)/3 ) ) \\ G. C. Greubel, Dec 01 2019

[-1]+[lucas_number1(n, 1, -2) for n in (1..35)] # G. C. Greubel, Dec 01 2019

a(n) = A001045(n), n>0.
a(n) + a(n+1) = 2*A001782(n) = 2*A131577(n) = A155559(n) = A090129(n+2), n>0.
G.f.: (2*x^2 + 2*x - 1)/((1+x)*(1-2*x)).
E.g.f.: (exp(2*x) - exp(-x) - 3)/3. - G. C. Greubel, Dec 01 2019

Edited and extended by R. J. Mathar, Nov 01 2009

A331691 Resultant of the Shapiro polynomials P_n(x) and Q_n(x).

Original entry on oeis.org

1, 2, -16, 2048, -67108864, 144115188075855872, -1329227995784915872903807060280344576, 226156424291633194186662080095093570025917938800079226639565593765455331328

Offset: 0

Kevin Ryde, Jan 24 2020

The Shapiro polynomials P_n(x) and Q_n(x) are defined by P_0(x) = Q_0(x) = 1 and then mutual recurrences P_{n+1}(x) = P_n(x) + x^(2^n)*Q_n(x) and Q_{n+1}(x) = P_n(x) - x^(2^n)*Q_n(x). The coefficients of P are the Golay-Rudin-Shapiro sequence A020985. a(n) is the polynomial resultant R(P_n(x),Q_n(x)) as considered by Brillhart and Carlitz.

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. Also at JSTOR. See A001782 for a scanned copy.
Harold S. Shapiro, Extremal Problems for Polynomials and Power Series, Masters Thesis, Massachusetts Institute of Technology, 1951. See pages 40-41.

Cf. A016031 (absolute values), A001782 (discriminant).

a(n) = if(n==0,1, -(-2)^(2^(n+1) - n - 2));

a(n) = my(P=1,Q=1); for(i=0,n-1, [P,Q]=[P+x^(2^i)*Q, P-x^(2^i)*Q]); polresultant(P,Q);

a(n) = (-1)^(n-1) * 2^(2^(n+1) - n - 2) for n >= 1 [Brillhart and Carlitz theorem 2].
a(n) = (-1)^(n-1) * A016031(n+2) for n >= 1.
a(n) = - 2^(2^n-1) * a(n-1) for n >= 2 [Brillhart and Carlitz in proof of theorem 2].

A229935 Total number of parts in all compositions of n with at least two parts in increasing order.

Original entry on oeis.org

0, 0, 0, 2, 8, 28, 77, 202, 490, 1152, 2624, 5869, 12913, 28116, 60660, 130004, 277065, 587859, 1242540, 2617942, 5500394, 11528284, 24109349, 50321442, 104844426, 218086957, 452963310, 939496802, 1946122511, 4026488387, 8321444573, 17179801049, 35433395265

Offset: 0

Omar E. Pol, Oct 14 2013

nonn

Total number of parts in all compositions of n that are not partitions of n (see example).

			For n = 4 the table shows both the compositions and the partitions of 4. There are three compositions of 4 that are not partitions of 4.
----------------------------------------------------
Compositions       Partitions       Number of parts
----------------------------------------------------
[1, 1, 1, 1]   =   [1, 1, 1, 1]
[2, 1, 1]      =   [2, 1, 1]
[1, 2, 1]                                 3
[3, 1]         =   [3, 1]
[1, 1, 2]                                 3
[2, 2]         =   [2, 2]
[1, 3]                                    2
[4]            =   [4]
----------------------------------------------------
Total                                     8
.
A partition of a positive integer n is any nonincreasing sequence of positive integers which sum to n, ence the compositions of 4 that are not partitions of 4 are [1, 2, 1], [1, 1, 2] and [1, 3]. The total number of parts of these compositions is 3 + 3 + 2 = 8. On the other hand the total number of parts in all compositions of 4 is A001792(4-1) = 20, and the total number of parts in all partitions of 4 is A006128(4) = 12, so a(4) = 20 - 12 = 8.

Cf. A000041, A001792, A006128, A001782, A056823, A229936.

a(n) = A001792(n-1) - A006128(n), n >= 1.

cp's OEIS Frontend

A014081 a(n) is the number of occurrences of '11' in the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Formula

A167167 A001045 with a(0) replaced by -1.

Views

Author

Keywords

Comments

Links

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A331691 Resultant of the Shapiro polynomials P_n(x) and Q_n(x).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

Formula

A229935 Total number of parts in all compositions of n with at least two parts in increasing order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula