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

Author

Darío Clavijo, Apr 21 2025

Keywords

• nonn
• base

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.

Examples

			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.
		

Crossrefs

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

Programs

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

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)])

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