cp's OEIS Frontend

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

%I A122953 #38 Sep 16 2024 09:22:53
%S A122953 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,
%T A122953 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,
%U A122953 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
%N A122953 a(n) = number of distinct positive integers represented in binary which are substrings of binary expansion of n.
%C A122953 a(n) = A078822(n) if n is of the form 2^k - 1. Otherwise, a(n) = A078822(n) - 1.
%C A122953 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)
%C A122953 Last occurrence of k: 2^k - 1.
%C A122953 a(n) = Sum_{k=1..n} A057427(A213629(n,k)). - _Reinhard Zumkeller_, Jun 17 2012
%C A122953 Length of n-th row in triangle A165416. - _Reinhard Zumkeller_, Jul 17 2015
%H A122953 Jeremy Gardiner, <a href="/A122953/b122953.txt">Table of n, a(n) for n = 1..2000</a>
%e A122953 Binary 1 = 1, binary 2 = 10, binary 4 = 100 and binary 9 = 1001 are all substrings of binary 9 = 1001. So a(9) = 4.
%p A122953 a:= n-> (s-> nops({seq(seq(parse(s[i..j]), i=1..j),
%p A122953     j=1..length(s))} minus {0}))(""||(convert(n, binary))):
%p A122953 seq(a(n), n=1..100);  # _Alois P. Heinz_, Jan 20 2021
%t A122953 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]
%o A122953 (Haskell)
%o A122953 a122953 = length . a165416_row
%o A122953 -- _Reinhard Zumkeller_, Jul 17 2015, Jan 22 2012
%o A122953 (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
%o A122953 (Python)
%o A122953 def a(n):
%o A122953   b = bin(n)[2:]
%o A122953   m = len(b)
%o A122953   return len(set(int(b[i:j]) for i in range(m) for j in range(i+1,m+1))-{0})
%o A122953 print([a(n) for n in range(1, 91)]) # _Michael S. Branicky_, Jan 20 2021
%Y A122953 Cf. A078822, A292924.
%Y A122953 Cf. A057427, A213629, A165416.
%K A122953 nonn,base
%O A122953 1,2
%A A122953 _Leroy Quet_, Oct 25 2006
%E A122953 More terms from _Robert G. Wilson v_, Nov 01 2006
%E A122953 Keyword base added by _Rémy Sigrist_, Mar 08 2018