A122953 a(n) = number of distinct positive integers represented in binary which are substrings of binary expansion of n.

1, 2, 2, 3, 3, 4, 3, 4, 4, 4, 5, 6, 6, 6, 4, 5, 5, 5, 6, 6, 5, 7, 7, 8, 8, 8, 8, 9, 9, 8, 5, 6, 6, 6, 7, 6, 7, 8, 8, 8, 8, 6, 8, 10, 9, 10, 9, 10, 10, 10, 10, 11, 10, 10, 11, 12, 12, 12, 12, 12, 12, 10, 6, 7, 7, 7, 8, 7, 8, 9, 9, 8, 7, 9, 10, 10, 11, 11, 10, 10, 10, 10, 11, 9, 7, 11, 11, 13, 13, 12

Offset: 1

Author

Leroy Quet, Oct 25 2006

Keywords

• nonn
• base

Comments

a(n) = A078822(n) if n is of the form 2^k - 1. Otherwise, a(n) = A078822(n) - 1.

First occurrence of k: 1, 2, 4, 6, 11, 12, 22, 24, 28, 44, 52, 56, 88, 92, 112, 116, 186, 184, 220, 232, 244, 368, 376, 440, 472, ... (See A292924 for the corresponding sequence. - Rémy Sigrist, Mar 09 2018)

Last occurrence of k: 2^k - 1.

a(n) = Sum_{k=1..n} A057427(A213629(n,k)). - Reinhard Zumkeller, Jun 17 2012

Length of n-th row in triangle A165416. - Reinhard Zumkeller, Jul 17 2015

Examples

			Binary 1 = 1, binary 2 = 10, binary 4 = 100 and binary 9 = 1001 are all substrings of binary 9 = 1001. So a(9) = 4.
		

Links

• Jeremy Gardiner, Table of n, a(n) for n = 1..2000

Crossrefs

Cf. A078822, A292924.

Cf. A057427, A213629, A165416.

Programs

Haskell

a122953 = length . a165416_row
-- Reinhard Zumkeller, Jul 17 2015, Jan 22 2012

Maple

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

Mathematica

f[n_] := Length@ Select[ Union[ FromDigits /@ Flatten[ Table[ Partition[ IntegerDigits[n, 2], i, 1], {i, Floor[ Log[2, n] + 1]}], 1]], # > 0 &]; Array[f, 90]

PARI

a(n) = my (v=0, s=0, x=Set()); while (n, my (r=n); while (r, if (r < 100 000, if (bittest(s,r), break, s+=2^r), if (setsearch(x,r), break, x=setunion(x, Set(r)))); v++; r \= 2); n -= 2^(#binary(n)-1)); v \\ Rémy Sigrist, Mar 08 2018

Python

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

Extensions

More terms from Robert G. Wilson v, Nov 01 2006

Keyword base added by Rémy Sigrist, Mar 08 2018