A078822 Number of distinct binary numbers contained as substrings in the binary representation of n.

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

Offset: 0

Author

Reinhard Zumkeller, Dec 08 2002

Keywords

• nonn
• base
• nice
• look

Comments

For n>0: 0A070939(n)+1, 0A070939(n). - Reinhard Zumkeller, Mar 07 2008

Row lengths in triangle A119709. - Reinhard Zumkeller, Aug 14 2013

Examples

			n=10 -> '1010' contains 5 different binary numbers: '0' (b0bb or bbb0), '1' (1bbb or bb1b), '10' (10bb or bb10), '101' (101b) and '1010' itself, therefore a(10)=5.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..16384 (first 1001 terms from Reinhard Zumkeller)

Crossrefs

Cf. A078823, A078826, A078824, A007088, A141297, A144623, A144624.

Programs

Haskell

a078822 = length . a119709_row
import Numeric (showIntAtBase)
-- Reinhard Zumkeller, Aug 13 2013, Sep 14 2011

Maple

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

Mathematica

a[n_] := (id = IntegerDigits[n, 2]; nd = Length[id]; Length[ Union[ Flatten[ Table[ id[[j ;; k]], {j, 1, nd}, {k, j, nd}], 1] //. {0, b__} :> {b}]]); Table[ a[n], {n, 0, 85}] (* Jean-François Alcover, Dec 01 2011 *)

PARI

a(n) = {if (n==0, 1, vb = binary(n); vf = []; for (i=1, #vb, for (j=1, #vb - i + 1, pvb = vector(j, k, vb[i+k-1]); f = subst(Pol(pvb), x, 2); vf = Set(concat(vf, f)); ); ); #vf); } \\ Michel Marcus, May 08 2016; corrected Jun 13 2022

Python

def a(n): return 1 if n == 0 else len(set(((((2<>i for i in range(n.bit_length()) for l in range(n.bit_length()-i)))
print([a(n) for n in range(64)]) # Michael S. Branicky, Jul 28 2022

Formula

For k>0: a(2^k-2) = 2*(k-1)+1, a(2^k-1) = k, a(2^k) = k+2;

for k>1: a(2^k+1) = k+2;

for k>0: a(2^k-1) = A078824(2^k-1), a(2^k) = A078824(2^k).