A122953 -id:A122953 - cp's OEIS frontend

A141297 a(n) = number of distinct (nonempty) substrings in the binary representation of n.

1, 3, 2, 5, 5, 5, 3, 7, 8, 7, 8, 8, 8, 7, 4, 9, 11, 11, 12, 11, 9, 11, 11, 11, 12, 11, 11, 11, 11, 9, 5, 11, 14, 15, 16, 14, 15, 16, 16, 15, 15, 11, 14, 16, 14, 15, 14, 14, 16, 16, 16, 16, 14, 14, 15, 15, 16, 15, 15, 14, 14, 11, 6, 13, 17, 19, 20, 19, 20, 21, 21, 19, 17, 19, 21, 20, 21

Offset: 1

Leroy Quet, Jun 24 2008

Substrings may start with a 0.
The terms were calculated by R. J. Mathar.
Also: "complexité par facteurs" of n written in base 2. [Alexandre Wajnberg, Aug 22 2011]

			The distinct substrings in binary representation (1010) of decimal 10 are 0,1,10,01,101,010,1010. So a(10) = 7.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Jean-Paul Delahaye, Le défi des faibles complexités, Pour la Science, 405 (2011), p. 82-87.

Cf. A078822, A141298, A141299, A141300, A122953.

a:= n-> (s-> nops({seq(seq(s[i..j], i=1..j),
    j=1..length(s))}))(""||(convert(n, binary))):
seq(a(n), n=1..84);  # Alois P. Heinz, Jan 20 2021

Table[With[{d = IntegerDigits[n, 2]}, Length@ Union@ Apply[Join, Table[Partition[d, k, 1], {k, Length@ d}]]], {n, 77}] (* Michael De Vlieger, Sep 22 2017 *)

def a(n):
  b = bin(n)[2:]
  m = len(b)
  return len(set(b[i:j] for i in range(m) for j in range(i+1, m+1)))
print([a(n) for n in range(1, 78)]) # Michael S. Branicky, Jan 20 2021

a(2^k - 1) = k - 1 for any k >= 0. - Rémy Sigrist, Jan 20 2021

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.

Original entry on oeis.org

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.

A300302 Square array T(n, k) (n >= 1, k >= 1) read by antidiagonals upwards: T(n, k) is the k-th positive number whose binary representation contains the binary representation of n as a substring.

Original entry on oeis.org

1, 2, 2, 3, 4, 3, 4, 6, 5, 4, 5, 8, 7, 6, 5, 6, 10, 9, 11, 8, 6, 7, 12, 11, 12, 12, 9, 7, 8, 14, 13, 13, 16, 13, 10, 8, 9, 16, 15, 14, 20, 17, 14, 11, 9, 10, 18, 17, 23, 22, 21, 18, 15, 12, 10, 11, 20, 19, 24, 28, 24, 22, 19, 19, 13, 11, 12, 22, 21, 25, 32, 29

Offset: 1

Rémy Sigrist, Mar 08 2018

Each positive number k appears A122953(k) times in this array.

			Square array begins:
  n\k|    1    2    3    4    5    6    7    8    9   10
  ---+--------------------------------------------------
    1|    1    2    3    4    5    6    7    8    9   10  <--  A000027
    2|    2    4    5    6    8    9   10   11   12   13  <--  A062289
    3|    3    6    7   11   12   13   14   15   19   22  <--  A004780
    4|    4    8    9   12   16   17   18   19   20   24  <--  A004753
    5|    5   10   11   13   20   21   22   23   26   27  <--  A004748
    6|    6   12   13   14   22   24   25   26   27   28  <--  A004749
    7|    7   14   15   23   28   29   30   31   39   46  <--  A004781
    8|    8   16   17   24   32   33   34   35   40   48  <--  A004779
    9|    9   18   19   25   36   37   38   39   41   50
   10|   10   20   21   26   40   41   42   43   52   53  <--  A132782

Rémy Sigrist, Perl program for A300302

Cf. A000027, A004748, A004749, A004753, A004779, A004780, A004781, A062289, A122953, A132782.

Perl
```
See Links section.
```

T(n, 1) = n.
T(n, 2) = 2*n.
T(n, 3) = 2*n + 1.
T(1, n) = A000027(n).
T(2, n) = A062289(n).
T(3, n) = A004780(n).
T(4, n) = A004753(n).
T(5, n) = A004748(n).
T(6, n) = A004749(n).
T(7, n) = A004781(n).
T(8, n) = A004779(n-1).
T(10, n) = A132782(n).

cp's OEIS Frontend

A141297 a(n) = number of distinct (nonempty) substrings in the binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

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

A300302 Square array T(n, k) (n >= 1, k >= 1) read by antidiagonals upwards: T(n, k) is the k-th positive number whose binary representation contains the binary representation of n as a substring.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Perl

Formula