login
A078822
Number of distinct binary numbers contained as substrings in the binary representation of n.
30
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
KEYWORD
nonn,base,nice,look
AUTHOR
Reinhard Zumkeller, Dec 08 2002
STATUS
approved