A383270 Length of the longest sequence of contiguous 1s in the binary expansion of n after flipping at most one 0-bit to 1.

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

Offset

0,3

Comments

There is only one allowed bit flip from 0 to 1 for each term, unless n is of the form 2^k-1 in which case a(n) = k.

At most one bit flip from 0 to 1 is allowed. If the original binary representation already contains the longest run of 1s, no flip is required.

Links

Table of n, a(n) for n=0..87.

Formula

a(n) <= 1 + floor(log_2(n)).

a(2^k-1) = k.

a(2^k) = 2 for k > 0.

a(2^k+1) = 2.

A038374(n) <= a(n) <= A000120(n)+1. - Michael S. Branicky, Apr 21 2025

Example

a(3) = 2 because 3 = 11_2 and there is no need to flip any bit.
a(1775) = 8 because 1775 = 11011101111_2 and if we flip the 7th bit we get 1101111111_2 which has the longest sequence of contiguous 1s of length 8.

Prog

(Python)
def a(n):
    if n == 0: return 1
    if n.bit_length() == n.bit_count(): return n.bit_length()
    c = p = m = 0
    while n:
        if n & 1: c += 1
        else:
            p = c * ((n & 2) > 0)
            c = 0
        if (pc := p + c) > m: m = pc
        n >>= 1
    return m + 1
print([a(n) for n in range(1, 88)])
(PARI) a(n) = if (n==0, return(1)); my(b=binary(n), vz = select(x->(x==0), b, 1), m=0); if (#vz <= 1, return (#b)); vz = concat(0, concat(Vec(vz), #b+1)); for (i=1, #vz-2, m = max(m, vz[i+2]-vz[i]-1)); m; \\ Michel Marcus, May 02 2025

Crossrefs

Cf. A000079, A000120, A007088, A070939, A038374.

Sequence in context: A177868 A178701 A181611 * A064740 A080967 A078570

Adjacent sequences: A383267 A383268 A383269 * A383271 A383272 A383273

Keyword

nonn,base

Author

Darío Clavijo, Apr 21 2025

Status

approved