A356150 -id:A356150 - cp's OEIS frontend

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

Rémy Sigrist, Jul 28 2022

Leading 0's in binary expansions are ignored.

			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.

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

Cf. A004277, A122953, A356149, A356150.

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

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

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

A356149 Irregular table T(n, k), n > 0, k = 1..A356148(n), read by rows; the n-th row contains, in ascending order, the distinct positive integers whose binary expansion appears as a substring in the binary expansion of n or its complement.

Original entry on oeis.org

1, 1, 2, 1, 3, 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 6, 1, 3, 7, 1, 2, 3, 4, 7, 8, 1, 2, 3, 4, 6, 9, 1, 2, 5, 10, 1, 2, 3, 4, 5, 11, 1, 2, 3, 4, 6, 12, 1, 2, 3, 5, 6, 13, 1, 2, 3, 6, 7, 14, 1, 3, 7, 15, 1, 2, 3, 4, 7, 8, 15, 16, 1, 2, 3, 4, 6, 7, 8, 14, 17, 1, 2, 3, 4, 5, 6, 9, 13, 18

Offset: 1

Rémy Sigrist, Jul 28 2022

Leading 0's in binary expansions are ignored.

The n-th contains the n-th row of A165416.

			Table T(n, k) begins:
    1;
    1, 2;
    1, 3;
    1, 2, 3, 4;
    1, 2, 5;
    1, 2, 3, 6;
    1, 3, 7;
    1, 2, 3, 4, 7, 8;
    1, 2, 3, 4, 6, 9;
    1, 2, 5, 10;
    1, 2, 3, 4, 5, 11;
    1, 2, 3, 4, 6, 12;
    1, 2, 3, 5, 6, 13;
    1, 2, 3, 6, 7, 14;
    1, 3, 7, 15;
    1, 2, 3, 4, 7, 8, 15, 16;
    ...

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

Cf. A165416, A356148, A356150.

row(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]) }

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

T(n, 1) = 1.

T(n, A356148(n)) = n.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula