A272604 -id:A272604 - cp's OEIS frontend

A384890 Number of maximal anti-runs (increasing by more than 1) in the binary indices of n.

0, 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, 3, 3, 3, 4, 5, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 2, 2, 2, 3, 4, 2, 2, 2, 3, 2, 2, 3, 4, 3, 3, 3, 4, 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

Offset: 0

Gus Wiseman, Jun 17 2025

nonn

First differs from A272604 at a(51) = 3, A272604(51) = 2.
A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.
Do all constant runs in this sequence have lengths 1, 2, or 3?

			The binary indices of 51 are {1,2,5,6}, with maximal anti-runs ((1),(2,5),(6)), so a(51) = 3.

For runs instead of anti-runs we have A069010 = run-lengths of A245563 (reverse A245562).
Row-lengths of A384877, firsts A384878.
For prime indices instead of binary indices we have A384906.
A000120 counts binary indices.
A356606 counts strict partitions without a neighborless part, complement A356607.
A384175 counts subsets with all distinct lengths of maximal runs, complement A384176.
Cf. A044813, A048793, A052499, A164707, A243815, A300820, A328592, A384177, A384879, A384893.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Table[Length[Split[bpe[n],#2!=#1+1&]],{n,0,100}]

A276691 Sum of maximum subrange sum over all length-n arrays of {1, -1}.

Original entry on oeis.org

1, 4, 11, 27, 63, 142, 314, 684, 1474, 3150, 6685, 14110, 29640, 62022, 129337, 268930, 557752, 1154164, 2383587, 4913835, 10113983, 20787252, 42668775, 87479539, 179157497, 366547820, 749256450, 1530251194, 3122882776, 6368433118, 12978230568, 26431617730, 53799078716, 109442256914, 222519713892, 452208698216, 918560947022, 1865036287632, 3785181059505, 7679199158098

Offset: 1

Jeffrey Shallit, Sep 13 2016

nonn

The maximum subrange sum of an array x = x[1..n] is the maximum possible value of the sum of the entries in x[a..b] for 1 <= a <= b <= n. The empty subrange has sum 0 and is also allowed. For example, the maximum subrange sum of (-1,1,1,1,-1,-1,1, 1, 1, -1) is 4.

Thus a(n)/2^n is the expected value of the maximum subrange sum. Heuristically this expected value should be approximately sqrt(n), but I don't have a rigorous proof.

			For n = 3, the maximum subrange sum of (-1,-1,-1) is 0 (the empty subrange); for (1 1 -1) and (-1 1 1) it is 2; for (1 1 1) it is 3; and for the 4 remaining arrays of length 3 it is 1.
Thus the sum is 3+(2*2)+4*1 = 11.

Joerg Arndt, C++ program for this sequence, (2016)
Jon Bentley, Programming pearls: algorithm design techniques, Communications of the ACM, (1984) 27 (9): 865-873.
discussion on Quora (not all comments there are correct)

Cf. A272604.

for n = 1:23
  L = 2*(dec2bin(0:2^n-1)-'0')-1;
  S = L * triu(ones(n,n+1),1);
  R = max(S,[],2);
  for i = 1:n
    R = max(R, max(S(:,i+1:n+1),[],2) - S(:,i));
  end
  A(n) = sum(R);
end
A  % Robert Israel, Sep 13 2016

a(20)-a(23) from Robert Israel, Sep 13 2016
a(24)-a(32) from Joerg Arndt, Sep 14 2016
a(33)-a(40) from Joerg Arndt, Sep 16 2016

cp's OEIS Frontend

A384890 Number of maximal anti-runs (increasing by more than 1) in the binary indices of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica