A038374 -id:A038374 - cp's OEIS frontend

A119706 Total length of longest runs of 1's in all bitstrings of length n.

1, 4, 11, 27, 62, 138, 300, 643, 1363, 2866, 5988, 12448, 25770, 53168, 109381, 224481, 459742, 939872, 1918418, 3910398, 7961064, 16190194, 32893738, 66772387, 135437649, 274518868, 556061298, 1125679616, 2277559414, 4605810806, 9309804278, 18809961926

Offset: 1

Adam Kertesz, Jun 09 2006, Jun 13 2006

nonn

a(n) divided by 2^n is the expected value of the longest run of heads in n tosses of a fair coin.

a(n) is also the sum of the number of binary words with at least one run of consecutive 0's of length >= i for i>=1. In other words A000225 + A008466 + A050231 + A050232 + ... . - Geoffrey Critzer, Jan 12 2013

			a(3)=11 because for the 8(2^3) possible runs 0 is longest run of heads once, 1 four times, 2 two times and 3 once and 0*1+1*4+2*2+3*1 = 11.

A. M. Odlyzko, Asymptotic Enumeration Methods, pp. 136-137
R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 372.

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.

Cf. A334833.

A038374 := proc(n) local nshft, thisr, resul; nshft := n ; resul :=0 ; thisr :=0 ; while nshft > 0 do if nshft mod 2 <> 0 then thisr := thisr+1 ; else resul := max(resul, thisr) ; thisr := 0 ; fi ; nshft := floor(nshft/2) ; od ; resul := max(resul, thisr) ; RETURN(resul) ; end : A119706 := proc(n) local count, c, rlen ; count := array(0..n) ; for c from 0 to n do count[c] := 0 ; od ; for c from 0 to 2^n-1 do rlen := A038374(c) ; count[rlen] := count[rlen]+1 ; od ; RETURN( sum('count[c]*c','c'=0..n) ); end: for n from 1 to 40 do print(n,A119706(n)) ; od : # R. J. Mathar, Jun 15 2006
# second Maple program:
b:= proc(n, m) option remember; `if`(n=0, 1,
      `if`(m=0, add(b(n-j, j), j=1..n),
      add(b(n-j, min(n-j, m)), j=1..min(n, m))))
    end:
a:= proc(n) option remember;
     `if`(n<2, n, 2*a(n-1) +b(n, 0))
    end:
seq(a(n), n=1..40);  # Alois P. Heinz, Dec 19 2014

nn=10;Drop[Apply[Plus,Table[CoefficientList[Series[1/(1-2x)-(1-x^n)/(1-2x+x^(n+1)),{x,0,nn}],x],{n,1,nn}]],1]  (* Geoffrey Critzer, Jan 12 2013 *)

a(n+1) = 2*a(n) + A007059(n+2)
a(n) > 2*a(n-1). a(n) = Sum_{i=1..(2^n)-1} A038374(i). - R. J. Mathar, Jun 15 2006
From Geoffrey Critzer, Jan 12 2013: (Start)
O.g.f.: Sum_{k>=1} 1/(1-2*x) - (1-x^k)/(1-2*x+x^(k+1)). - Corrected by Steven Finch, May 16 2020
a(n) = Sum_{k=1..n} A048004(n,k) * k.
(End)
Conjecture: a(n) = A102712(n+1)-2^n. - R. J. Mathar, Jun 05 2025

More terms from R. J. Mathar, Jun 15 2006

Name edited by Alois P. Heinz, Mar 18 2020

A330036 The length of the largest run of 0's in the binary expansion of n + the length of the largest run of 1's in the binary expansion of n.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 3, 3, 4, 3, 2, 3, 4, 3, 4, 4, 5, 4, 3, 4, 3, 2, 3, 4, 5, 4, 3, 3, 5, 4, 5, 5, 6, 5, 4, 5, 3, 3, 4, 5, 4, 3, 2, 3, 4, 3, 4, 5, 6, 5, 4, 4, 4, 3, 3, 4, 6, 5, 4, 4, 6, 5, 6, 6, 7, 6, 5, 6, 4, 4, 5, 6, 4, 3, 3, 4, 4, 4, 5, 6, 5, 4, 3

Offset: 0

Joshua Oliver, Nov 27 2019

All numbers appear in this sequence. The number of 1's in the n-th Mersenne number (A000225) is n and the number of 0's in the n-th Mersenne number is 0. 0+n=n. See formula.

			   n [binary n ]  A087117(n) + A038374(n) = a(n)
   0 [       0 ]  1          + 0          = 1
   1 [       1 ]  0          + 1          = 1
   2 [     1 0 ]  1          + 1          = 2
   3 [     1 1 ]  0          + 2          = 2
   4 [   1 0 0 ]  2          + 1          = 3
   5 [   1 0 1 ]  1          + 1          = 2
   6 [   1 1 0 ]  1          + 2          = 3
   7 [   1 1 1 ]  0          + 3          = 3
   8 [ 1 0 0 0 ]  3          + 1          = 4
   9 [ 1 0 0 1 ]  2          + 1          = 3
  10 [ 1 0 1 0 ]  1          + 1          = 2
  11 [ 1 0 1 1 ]  1          + 2          = 3
  12 [ 1 1 0 0 ]  2          + 2          = 4
  13 [ 1 1 0 1 ]  1          + 2          = 3
  14 [ 1 1 1 0 ]  1          + 3          = 4
  15 [ 1 1 1 1 ]  0          + 4          = 4

Robert Israel, Table of n, a(n) for n = 0..10000

Cf. A000120, A000225, A007088, A023416, A038374, A087117.

f:= proc(n) local L;
  L:= convert(n,base,2);
  max(map(nops,[ListTools:-Split(`=`,L,1)]))+max(map(nops,[ListTools:-Split(`=`,L,0)]))
end proc:
map(f, [$0..100]); # Robert Israel, Apr 06 2020

Table[Sum[Max[Differences[Position[Flatten@{k,IntegerDigits[n,2],k},k]]],{k,0,1}]-2,{n,0,82}]

a(n) = A087117(n) + A038374(n).

a(A000225(n)) = n for n > 0.

A090001 Length of longest contiguous block of 1's in binary expansion of n^2.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 4, 1, 1, 2, 3, 1, 1, 1, 2, 2, 3, 4, 1, 1, 3, 1, 2, 2, 2, 3, 4, 1, 1, 1, 2, 1, 2, 2, 5, 2, 2, 3, 3, 4, 6, 1, 1, 1, 2, 3, 1, 1, 5, 2, 4, 2, 2, 2, 2, 3, 3, 4, 5, 1, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 6, 2, 3, 5, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 6, 2, 1, 3, 1, 2, 1, 2, 2, 2, 3, 5

Offset: 0

Reinhard Zumkeller, Nov 20 2003

a(n) = A038374(A000290(n)).

Harvey P. Dale, Table of n, a(n) for n = 0..1000

Cf. A000120, A090003, A090002, A090000, A089998, A090047.

Join[{0},Table[Max[Length/@Select[Split[IntegerDigits[n^2,2]], MemberQ[ #,1]&]],{n,110}]] (* Harvey P. Dale, Nov 28 2014 *)

A090002 Length of longest contiguous block of 1's in binary expansion of n-th triangular number.

Original entry on oeis.org

0, 1, 2, 2, 1, 4, 1, 3, 1, 2, 3, 1, 3, 2, 2, 4, 1, 2, 2, 5, 2, 3, 6, 1, 2, 1, 5, 4, 2, 2, 3, 5, 1, 2, 2, 3, 2, 6, 3, 2, 2, 3, 3, 3, 4, 2, 3, 2, 2, 2, 5, 3, 2, 3, 3, 2, 4, 3, 4, 3, 3, 3, 4, 6, 1, 2, 2, 3, 1, 4, 2, 7, 1, 2, 3, 2, 3, 3, 2, 2, 2, 5, 2, 4, 5, 3, 3, 4, 4, 5, 12, 2, 2, 2, 3, 3, 2, 1, 4, 2, 3, 5

Offset: 0

Reinhard Zumkeller, Nov 20 2003

a(n) = A038374(A000217(n)).

Antti Karttunen, Table of n, a(n) for n = 0..16384
Index entries for sequences related to binary expansion of n

Cf. A000120, A090001, A090003, A089999, A090048.

Join[{0},Max[Length/@Select[Split[IntegerDigits[#,2]],#[[1]]==1&]]&/@ Accumulate[ Range[110]]] (* Harvey P. Dale, Jul 28 2022 *)

A090000 Length of longest contiguous block of 1's in binary expansion of n-th prime.

Original entry on oeis.org

1, 2, 1, 3, 2, 2, 1, 2, 3, 3, 5, 1, 1, 2, 4, 2, 3, 4, 2, 3, 1, 4, 2, 2, 2, 2, 3, 2, 2, 3, 7, 2, 1, 2, 1, 3, 3, 2, 3, 2, 2, 2, 6, 2, 2, 3, 2, 5, 3, 3, 3, 4, 4, 5, 1, 3, 2, 4, 1, 2, 2, 1, 2, 3, 3, 4, 2, 1, 2, 3, 2, 3, 4, 3, 4, 7, 2, 2, 2, 2, 2, 2, 4, 2, 3, 3, 3, 3, 3, 4, 3, 5, 4, 4, 5, 5, 7, 1, 2, 3, 2, 2, 2, 3, 3

Offset: 1

Reinhard Zumkeller, Nov 20 2003

a(n) = A038374(A000040(n)).

John Mason, Table of n, a(n) for n = 1..20000

Cf. A000120, A004676, A090001, A090002, A090003, A090046, A090593.

f[n_] := Length[ Union[ DeleteCases[ Split[ IntegerDigits[n, 2]], 0, 2]][[ -1]]]; Table[ f[ Prime[n]], {n, 1, 105}] (* Robert G. Wilson v, Dec 04 2003 *)

A090003 Length of longest contiguous block of 1's in binary expansion of n^3.

Original entry on oeis.org

0, 1, 1, 2, 1, 5, 2, 3, 1, 2, 5, 2, 2, 1, 3, 4, 1, 2, 2, 2, 5, 2, 2, 5, 2, 4, 1, 3, 3, 5, 4, 5, 1, 2, 2, 4, 2, 3, 2, 4, 5, 3, 2, 2, 2, 6, 5, 4, 2, 3, 4, 2, 1, 2, 3, 4, 3, 2, 5, 2, 4, 3, 5, 6, 1, 2, 2, 2, 2, 4, 4, 3, 2, 5, 3, 8, 2, 4, 4, 4, 5, 6, 3, 3, 2, 4, 2, 3, 2, 3, 6, 8, 5, 2, 4, 5, 2, 4, 3, 3, 4, 5

Offset: 0

Reinhard Zumkeller, Nov 20 2003

a(n) = A038374(A000578(n)).

Antti Karttunen, Table of n, a(n) for n = 0..16384
Index entries for sequences related to binary expansion of n

Cf. A000120, A090001, A090002, A090049.

Join[{0},Table[Max[Length/@Select[Split[IntegerDigits[n^3,2]],MemberQ[#,1]&]],{n,110}]] (* Harvey P. Dale, Aug 28 2016 *)

A038374(n) = { if(n<2, return(n)); n>>=valuation(n, 2); if(n<2, return(n)); my(e=valuation(n+1, 2)); max(e, A038374(n>>e)); } \\ After Charles R Greathouse IV, Jan 12 2014
A090003(n) = A038374(n^3); \\ Antti Karttunen, Jul 09 2017

A144790 Consider the runs of 1's in the binary representation of n, each of these runs being on the edge of the binary representation n and/or being bounded by 0's. a(n) = the length of the shortest such run of 1's in binary n.

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 1, 2, 1, 3, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 4, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 3, 1, 1, 2, 4, 1, 5, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 1

Offset: 1

Leroy Quet, Sep 21 2008

			19 in binary is 10011. The runs of 1's are as follows: (1)00(11). The shortest of these runs contains exactly one 1. So a(19) = 1.

Michael De Vlieger, Table of n, a(n) for n = 1..16384

Cf. A038374, A144789.

Array[Min@ Map[Length, Select[Split@ IntegerDigits[#, 2], First@ # == 1 &]] &, 105] (* Michael De Vlieger, Oct 26 2017 *)

Extended by Ray Chandler, Nov 04 2008

A284569 a(n) = LCM of the lengths of runs of 1-bits in binary representation of n.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 2, 2, 2, 3, 4, 1, 1, 1, 2, 1, 1, 2, 3, 2, 2, 2, 2, 3, 3, 4, 5, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 2, 2, 2, 3, 4, 2, 2, 2, 2, 2, 2, 2, 6, 3, 3, 3, 6, 4, 4, 5, 6, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 2, 2, 2, 3, 4, 1, 1, 1, 2, 1, 1, 2, 3, 2, 2, 2, 2, 3, 3, 4, 5, 2, 2, 2, 2, 2, 2, 2, 6, 2, 2, 2, 2, 2, 2, 6, 4, 3, 3, 3, 6, 3, 3, 6, 3, 4

Offset: 0

Antti Karttunen, Apr 14 2017

			For n = 27, in binary A007088(27) = "11011", the lengths of runs of 1-bits are [2,2], thus a(27) = lcm(2,2) = 2.
For n = 55, in binary A007088(55) = "110111", the lengths of runs of 1-bits are [2,3], thus a(55) = lcm(2,3) = 6.

Antti Karttunen, Table of n, a(n) for n = 0..10922
Index entries for sequences related to binary expansion of n

Cf. A005940, A072411, A227349, A284562, A284559.
Cf. A003714 (positions of ones).
Differs from A227349 for the first time at n=27, where a(27)=2, while A227349(27)= 4.
Differs from A038374 for the first time at n=55, where a(55) = 6, while A038374(55) = 3.

(define (A284569 n) (apply lcm (bisect (reverse (binexp->runcount1list n)) (- 1 (modulo n 2))))) ;; For bisect and binexp->runcount1list, see the Program section of A227349.
(define (A284569 n) (A072411 (A005940 (+ 1 n))))

a(n) = A072411(A005940(1+n)).

a(n) = A227349(n) / A284562(n).

A179821 In binary representation of n: replace all blocks of k contiguous ones with binary representation of k.

Original entry on oeis.org

0, 1, 2, 2, 4, 5, 4, 3, 8, 9, 10, 10, 8, 9, 6, 4, 16, 17, 18, 18, 20, 21, 20, 11, 16, 17, 18, 18, 12, 13, 8, 5, 32, 33, 34, 34, 36, 37, 36, 19, 40, 41, 42, 42, 40, 41, 22, 20, 32, 33, 34, 34, 36, 37, 36, 19, 24, 25, 26, 26, 16, 17, 10, 6, 64, 65, 66, 66, 68, 69, 68, 35, 72, 73, 74, 74

Offset: 0

Reinhard Zumkeller, Jul 31 2010

a(n) <= n:
a(A003714(n)) = A003714(n); a(A004780(n)) < A004780(n);
A090077(n) <= a(n).

			n=45->101101->[1]0[11]0[1]->[1]0[2]0[1]->[1]0[10]0[1]->101001->a(45)=41.

Cf. A038374, A069010, A000120, A000225, A007088.

a(2*n) = 2*a(n); a(4*n+1) = 4*a(n)+1.

A374176 a(n) is the maximum number of consecutive bit changes in the binary representation of n.

Original entry on oeis.org

0, 1, 0, 1, 2, 1, 0, 1, 1, 3, 2, 1, 2, 1, 0, 1, 1, 2, 1, 3, 4, 2, 2, 1, 1, 3, 2, 1, 2, 1, 0, 1, 1, 2, 1, 2, 3, 1, 1, 3, 3, 5, 4, 2, 2, 2, 2, 1, 1, 2, 1, 3, 4, 2, 2, 1, 1, 3, 2, 1, 2, 1, 0, 1, 1, 2, 1, 2, 3, 1, 1, 2, 2, 4, 3, 1, 2, 1, 1, 3, 3, 3, 3, 5, 6, 4, 4, 2, 2, 3, 2, 2, 2, 2, 2, 1, 1, 2, 1, 2, 3, 1, 1, 3, 3

Offset: 1

Hugo Pfoertner, Jul 05 2024

			a(1117) = 3:
  1117_2 = [1 0 0 0 1 0 1 1 1 0 1]
             ^     ^ ^ ^     ^ ^
             1       3        2
            consecutive changes

Hugo Pfoertner, Table of n, a(n) for n = 1..8192

Cf. A005811, A037834, A038554, A038374.

Cf. A000975 (index of first occurrence of n).

b:= n-> `if`(n<2, [0$2], (f-> (t-> [t, max(t, f[2])])(
        `if`(n mod 4 in {0, 3}, 0, f[1]+1)))(b(iquo(n, 2)))):
a:= n-> b(n)[2]:
seq(a(n), n=1..105);  # Alois P. Heinz, Jul 07 2024

a(n) = {my(b=digits(n,2), d=#b, m=0, j=b[1], c=0); for(k=2, d, if(b[k]!=j, c++; m=max(m,c), c=0); j=b[k]); m}

def a(n):
    b, c, m = bin(n)[2:], 0, 0
    for i in range(len(b)-1):
        if b[i] != b[i+1]: c += 1
        else: m = max(m, c); c = 0
    return max(m, c)
print([a(n) for n in range(1, 89)]) # Michael S. Branicky, Jul 06 2024

# using formula
from itertools import groupby
def a(n): return max((len(list(g)) for k, g in groupby(bin(n^(n>>1))[3:]) if k=="1"), default=0)
print([a(n) for n in range(1, 89)]) # Michael S. Branicky, Jul 06 2024

a(n) = A038374(A038554(n)), with A038374(0) = 0. - Michael S. Branicky, Jul 06 2024

cp's OEIS Frontend

A119706 Total length of longest runs of 1's in all bitstrings of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A330036 The length of the largest run of 0's in the binary expansion of n + the length of the largest run of 1's in the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A090001 Length of longest contiguous block of 1's in binary expansion of n^2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A090002 Length of longest contiguous block of 1's in binary expansion of n-th triangular number.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A090000 Length of longest contiguous block of 1's in binary expansion of n-th prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A090003 Length of longest contiguous block of 1's in binary expansion of n^3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A144790 Consider the runs of 1's in the binary representation of n, each of these runs being on the edge of the binary representation n and/or being bounded by 0's. a(n) = the length of the shortest such run of 1's in binary n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A284569 a(n) = LCM of the lengths of runs of 1-bits in binary representation of n.

Views

Author

Keywords

Examples

Links