cp's OEIS Frontend

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

%I A078822 #40 Jul 31 2022 07:47:23
%S A078822 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,
%T A078822 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,
%U A078822 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
%N A078822 Number of distinct binary numbers contained as substrings in the binary representation of n.
%C A078822 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
%C A078822 Row lengths in triangle A119709. - _Reinhard Zumkeller_, Aug 14 2013
%H A078822 Alois P. Heinz, <a href="/A078822/b078822.txt">Table of n, a(n) for n = 0..16384</a> (first 1001 terms from Reinhard Zumkeller)
%F A078822 For k>0: a(2^k-2) = 2*(k-1)+1, a(2^k-1) = k, a(2^k) = k+2;
%F A078822 for k>1: a(2^k+1) = k+2;
%F A078822 for k>0: a(2^k-1) = A078824(2^k-1), a(2^k) = A078824(2^k).
%e A078822 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.
%p A078822 a:= n-> (s-> nops({seq(seq(parse(s[i..j]), i=1..j),
%p A078822         j=1..length(s))}))(""||(convert(n, binary))):
%p A078822 seq(a(n), n=0..85);  # _Alois P. Heinz_, Jan 20 2021
%t A078822 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 *)
%o A078822 (Haskell)
%o A078822 a078822 = length . a119709_row
%o A078822 import Numeric (showIntAtBase)
%o A078822 -- _Reinhard Zumkeller_, Aug 13 2013, Sep 14 2011
%o A078822 (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
%o A078822 (Python)
%o A078822 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)))
%o A078822 print([a(n) for n in range(64)]) # _Michael S. Branicky_, Jul 28 2022
%Y A078822 Cf. A078823, A078826, A078824, A007088, A141297, A144623, A144624.
%K A078822 nonn,base,nice,look
%O A078822 0,3
%A A078822 _Reinhard Zumkeller_, Dec 08 2002