A014083 Occurrences of '1111' in binary expansion of n.

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 0

Author

Simon Plouffe

Keywords

• nonn
• base
• easy

Examples

			a(63) = 3 as 63 = 111111 in binary and 1111 occurs three times (different occurrences may overlap). - _Antti Karttunen_, Jul 24 2017
		

Links

• Antti Karttunen, Table of n, a(n) for n = 0..65536
• R. Stephan, Some divide-and-conquer sequences ...
• R. Stephan, Table of generating functions
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A000120, A014081, A014082.

Programs

Maple

See A014081.

Mathematica

Table[SequenceCount[IntegerDigits[n,2],{1,1,1,1},Overlaps->True],{n,0,100}] (* The program uses the SequenceCount function from Mathematica version 10 *) (* Harvey P. Dale, Sep 25 2015 *)

PARI

u1111(n)=my(v=binary(n)); sum(k=1,#v-3, v[k]&&v[k+1]&&v[k+2]&&v[k+3])

PARI

a(n)=my(s,t); while(n, n>>=valuation(n,2); t=valuation(n+1,2); s+=max(t-3, 0); n>>=t); s \\ Charles R Greathouse IV, Jan 21 2016

Formula

a(2n) = a(n), a(2n+1) = a(n) + [n congruent to 7 mod 8]. - Ralf Stephan, Aug 21 2003

G.f.: 1/(1-x) * sum(k>=0, t^15(1-t)/(1-t^16), t=x^2^k). - Ralf Stephan, Sep 08 2003

a(n) <= log_2(n+1) - 3 for n >= 7. - Charles R Greathouse IV, Jan 21 2016

Extensions

Term a(0)=0 prepended and more terms from Antti Karttunen, Jul 24 2017