A245195 -id:A245195 - 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

A245180 A160239(n)/8.

Original entry on oeis.org

1, 1, 3, 1, 8, 3, 14, 1, 8, 8, 24, 3, 24, 14, 52, 1, 8, 8, 24, 8, 64, 24, 112, 3, 24, 24, 72, 14, 112, 52, 216, 1, 8, 8, 24, 8, 64, 24, 112, 8, 64, 64, 192, 24, 192, 112, 416, 3, 24, 24, 72, 24, 192, 72, 336, 14, 112, 112, 336, 52, 416, 216, 848, 1, 8, 8, 24, 8, 64, 24, 112, 8, 64, 64, 192

Offset: 1

N. J. A. Sloane, Jul 16 2014

			The entries may be arranged into blocks of sizes 1,2,4,8,...:
B_0: 1,
B_1: 1, 3,
B_2: 1, 8, 3, 14,
B_3: 1, 8, 8, 24, 3, 24, 14, 52,
B_4: 1, 8, 8, 24, 8, 64, 24, 112, 3, 24, 24, 72, 14, 112, 52, 216,
B_5: 1, 8, 8, 24, 8, 64, 24, 112, 8, 64, 64, 192, 24, 192, 112, 416, 3, 24, 24, 72, 24, 192, 72, 336, 14, 112, 112, 336, 52, 416, 216, 848,
...
The first half of each block is equal to 1 followed by 8 times an initial segment of the sequence itself.
The next quarter of each block consists of 3 times (1 followed by 8 times an initial segment of the sequence itself).
The next one-eighth of each block consists of 14 times (1 followed by 8 times an initial segment of the sequence itself).
And so on, the successive multipliers 1,3,14,52,... being given by A083424.
Also, the final quarter of any block consists of the twice the last half of the previous block added to eight times the full block before that.
Consider for example the 4th block,
[1, 8, 8, 24, 8, 64, 24, 112; 3, 24, 24, 72; 14, 112, 52, 216].
This is [1 8*(1,1,3,1,8,3,14); 3*(1 8*(1,1,3)); 2*(3,24,14,52)+8*(1,8,3,14)].
The final entries in the blocks give A083424.
See also the formula section.
.
From _Omar E. Pol_, Mar 18 2015: (Start)
Also, the sequence can be written as an irregular tetrahedron T(s,r,k) as shown below:
1;
..
1;
3;
........
1,    8;
3;
14;
................
1,    8,  8, 24;
3,   24;
14;
52;
..................................
1,    8,  8, 24,  8,  64, 24, 112;
3,   24, 24, 72;
14, 112;
52;
216;
.....................................................................
1,    8,  8, 24,  8,  64, 24, 112, 8, 64, 64, 192, 24, 192, 112, 416;
3,   24, 24, 72, 24, 192, 72, 336;
14, 112,112,336;
52, 416;
216;
848;
...
Note that T(s,r,k) = T(s+1,r,k).
(End)

N. J. A. Sloane, Table of n, a(n) for n = 1..16383
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.], which is also available at arXiv:1004.3036v2

Cf. A160239, A083424, A245190, A245195, A245196, A245562, A245540 (partial sums).

See A245181 for the numbers that appear.

a245180 = flip div 8 . a160239  -- Reinhard Zumkeller, Feb 13 2015

R:=proc(n) option remember;
if n=1 then 1
elif (n mod 2) = 0 then R(n/2)
elif (n mod 4) = 3 then 2*R((n-1)/2)+R(n-2)
else 8*R((n-1)/4); fi; end;
[seq(R(n),n=1..200)];

R[n_] := R[n] = Which[n == 1, 1, Mod[n, 2] == 0, R[n/2], Mod[n, 4] == 3, 2*R[(n - 1)/2] + R[n - 2], True, 8*R[(n - 1)/4] ];
Array[R, 200] (* Jean-François Alcover, Nov 16 2017, translated from Maple *)

The following is a fairly simple explicit formula for a(n) as a function of n: a(n) = 8^(r-1) * Product_{lengths i of runs of 1 in binary expansion of n} R(i), where r is the number of runs of 1 in the binary expansion of n and R(i) = A083424(i-1) = (5*4^(i-1)+(-2)^(i-1))/6. Note that row i of the table in A245562 lists the lengths of runs of 1 in binary expansion of i. Example: n = 27 = 11011 in binary, there are two runs each of length 2, so r=1, R(2) = A083424(1) = 3, and so a(27) = 8^1*3*3 = 72. - N. J. A. Sloane, Aug 10 2014
Many 2-D cellular automata studied in the Toothpick paper (Applegate et al.) have a recursive formula for the general term in a typical block of 2^k terms (see Equations 2, 4, 5, 9, 10 12, 38, 39 of that paper). An analogous formula for the present sequence is the following.
Consider the block B_{k-1} containing terms a(2^(k-1)), a(2^(k-1)+1), ..., a(2^k-1). It is convenient to index the terms working backwards from the next, 2^k-th, term. For n in the range 2^(k-1) <= n < 2^k, write n = 2^k-2^r+j, with 0 <= r <= k-1 and 0 <= j < 2^(r-1), and j=0 if r=0. Then
(if j=0) a(2^k-2^r) = f(k-r-1),
(if j>0) a(2^k-2^r+j) = 8*f(k-r-1)*a(j),
where f(i) = A083424(i) = (5*4^i+(-2)^i)/6.
For example, here is block B_4, consisting of terms a(16)=a(31), so k=5:
n:   16 17 18 19 20 21 22 23 24 25 26 27 28  29 30 31
a(n): 1  8  8 24  8 64 24 112 3 24 24 72 14 112 52 216
r:    4  4  4  4  4  4  4  4  3  3  3  3  2   2  1  0
j:    0  1  2  3  4  5  6  7  0  1  2  3  0   1  0  0
Then we have a(24) = a(32-8) = f(5-3-1) = f(1) = 3, illustrating the first equation, and a(21) = a(32-16+5) = 8*f(0)*a(5) = 8*1*8 = 64, illustrating the second equation.
See A245196 for a list of sequences produced by this type of recurrence.

A245196 Write n>=1 as either n=2^k-2^r with 0 <= r <= k-1, in which case a(2^k-2^r)=wt(k-r-1), or as n=2^k-2^r+j with 2 <= r <= k-1, 1 <= j < 2^r-1, in which case a(2^k-2^r+j)=a(j)*wt(k-r-1) (where wt(i) = A000120(i)).

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Jul 25 2014

Other sequences defined by a recurrence of this class (see the Formula and Maple sections) include A245180, A245195, A048896, A245536, A038374.

			May be arranged into blocks of lengths 1,2,4,8,...:
0,
0, 1,
0, 0, 1, 1,
0, 0, 0, 0, 1, 0, 1, 2,
0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 2, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 2, 0, 1, 2,
...

Cf. A000120, A160239, A245180, A245195, A014081, A048896, A038374, A245536, A245537, A245538, A245539, A048896, A245547.

Maple code for this sequence:
wt := proc(n) local w, m, i; w := 0; m := n; while m > 0 do i := m mod 2; w := w+i; m := (m-i)/2; od; w; end:
G:=[seq(wt(n),n=0..30)];
m:=1;
f:=proc(n) option remember; global m,G; local k,r,j,np;
   k:=1+floor(log[2](n)); np:=2^k-n;
   if np=1 then r:=0; j:=0; else r:=1+floor(log[2](np-1)); j:=2^r-np; fi;
   if j=0 then G[k-r]; else m*G[k-r]*f(j); fi;
end;
[seq(f(n),n=1..120)];
# Maple code for the general recurrence:
G:=[seq(wt(n),n=0..30)]; # replace this by a list G=[G(0), G(1), G(2), ...], remembering that you have to tell Maple G[1] to get G(0), G[2] to get G(1), etc.
m:=1; # replace this by the correct multiplier
f:=proc(n) option remember; global m,G; local k,r,j,np;
   k:=1+floor(log[2](n)); np:=2^k-n;
   if np=1 then r:=0; j:=0; else r:=1+floor(log[2](np-1)); j:=2^r-np; fi;
   if j=0 then G[k-r-1+1]; else m*G[k-r-1+1]*f(j); fi;
end;
[seq(f(n),n=1..120)];
# If G(n) = wt(n) and m=1 we get the present sequence
# If G(n) = A083424(n) and m=1 we get A245537
# If G(n) = A083424(n) and m=2 we get A245538
# If G(n) = A083424(n) and m=4 we get A245539
# If G(n) = A083424(n) and m=8 we get A245180 (and presumably A160239)
# If G(n) = n (n>=0) and m=1 we get A245536
# If G(n) = n+1 (n>=0) and m=1 we get A038374
# If G(n) = (n+1)(n+2)/2 (n>=0) and m=1 we get A245541
# If G(n) = (n+1)(n+2)/2 (n>=0) and m=2 we get A245547
# If G(n) = 2^n (n>=0) and m=1 we get A245195 (= 2^A014081)
# If G(n) = 2^n (n>=0) and m=2 we get A048896

This is an example of a class of sequences defined by the following recurrence.
We first choose a sequence G = [G(0), G(1), G(2), G(3), ...], which are the terms that will appear at the ends of the blocks: a(2^k-1) = G(k-1), and we also choose a parameter m (the "multiplier"). Then the recurrence (this defines a(1), a(2), a(3), ...) is:
a(2^k-2^r)=G(k-r-1) if 0 <= r <= k-1, a(2^k-2^r+j)=m*a(j)*G(k-r-1) if 2 <= r <= k-1, 1 <= j < 2^r-1.
To help apply the recurrence, here are the values of k,r,j for the first few values of n (if n=2^k-2^r we set j=0, although it is not used):
n:  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
k:  1  2  2  3  3  3  3  4  4  4  4  4  4  4  4
r:  0  1  0  2  2  1  0  3  3  3  3  2  2  1  0
j:  0  0  0  0  1  0  0  0  1  2  3  0  1  0  0
--------------------------------------------------
n: 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
k:  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
r:  4  4  4  4  4  4  4  4  3  3  3  3  2  2  1  0
j:  0  1  2  3  4  5  6  7  0  1  2  3  0  1  0  0
--------------------------------------------------
In the present example G(n) = wt(n) and m=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

A245180 A160239(n)/8.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

A245196 Write n>=1 as either n=2^k-2^r with 0 <= r <= k-1, in which case a(2^k-2^r)=wt(k-r-1), or as n=2^k-2^r+j with 2 <= r <= k-1, 1 <= j < 2^r-1, in which case a(2^k-2^r+j)=a(j)*wt(k-r-1) (where wt(i) = A000120(i)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula