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,2

Comments

Leading 0's in binary expansions are ignored.

Links

Rémy Sigrist, Table of n, a(n) for n = 1..8192

Index entries for sequences related to binary expansion of n

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.

Example

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.

Prog

(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<<N)-1)^n, set()
    for i in range(N):
        for l in range(N-i):
            mask = ((2<<l)-1) << i
            s.add((mask&n) >> 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

Crossrefs

Cf. A004277, A122953, A356149, A356150.

Sequence in context: A224901 A366651 A274176 * A083742 A107331 A283187

Adjacent sequences: A356145 A356146 A356147 * A356149 A356150 A356151

Keyword

nonn,base

Author

Rémy Sigrist, Jul 28 2022

Status

approved