A356148 a(n) is the number of positive integers whose binary expansion appears as a substring in the binary expansion of n or its complement.

1, 2, 2, 4, 3, 4, 3, 6, 6, 4, 6, 6, 6, 6, 4, 8, 9, 9, 8, 8, 5, 9, 9, 9, 8, 8, 9, 9, 9, 8, 5, 10, 12, 13, 12, 12, 12, 10, 12, 12, 12, 6, 10, 12, 12, 13, 12, 12, 12, 12, 10, 12, 10, 12, 13, 12, 12, 12, 13, 12, 12, 10, 6, 12, 15, 17, 16, 17, 17, 16, 15, 17, 15

Offset: 1

Author

Rémy Sigrist, Jul 28 2022

Keywords

• nonn
• base

Comments

Leading 0's in binary expansions are ignored.

Examples

			For n = 43:
- the binary expansion of 43 is "101011",
- it contains the positive numbers with binary expansions "1", "10", "11", "101", "1010", "1011", "10101", "101011",
- the complement of "101011" is "010100",
- it contains the positive numbers with binary expansions "1", "10", "100", "101", "1010", "10100",
- all in all, we have the following substrings: "1", "10", "11", "100", "101", "1010", "1011", "10100", "10101", "101011",
- so a(43) = 10.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..8192
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A004277, A122953, A356149, A356150.

Programs

PARI

a(n) = { my (b=binary(n)); #setbinop((i,j) -> my (s=fromdigits(b[i..j], 2)); if (b[i], s, 2^(j-i+1)-1-s), [1..#b]) }

Python

def a(n):
    N = n.bit_length()
    c, s = ((1<> i)
            s.add((mask&c) >> i)
    return len(s - {0})
print([a(n) for n in range(1, 74)]) # Michael S. Branicky, Jul 28 2022

Formula

a(n) >= A122953(n).

a(2^k-1) = 2^k-1 for any k >= 0.

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