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

Author

Leroy Quet, Jun 24 2008

Keywords

• nonn
• look
• base

Comments

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]

Examples

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

Links

• 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.

Crossrefs

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

Programs

Maple

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

Mathematica

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

Python

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

Formula

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