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,3

Comments

For n>0: 0<a(2*n)-a(n)<=A070939(n)+1, 0<a(2*n+1)-a(n) < A070939(n). - Reinhard Zumkeller, Mar 07 2008

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

Links

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

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

Example

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.

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

Prog

(Haskell)
a078822 = length . a119709_row
import Numeric (showIntAtBase)
-- Reinhard Zumkeller, Aug 13 2013, Sep 14 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<<l)-1)<<i)&n)>>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

Crossrefs

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

Sequence in context: A322349 A321232 A326015 * A224980 A368677 A154392

Adjacent sequences: A078819 A078820 A078821 * A078823 A078824 A078825

Keyword

nonn,base,nice,look

Author

Reinhard Zumkeller, Dec 08 2002

Status

approved