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