cp's OEIS Frontend

A356148 a(n) is the number of positive integers whose binary expansion appears as a substring in the binary expansion of n or its complement.

%I A356148 #12 Jul 31 2022 19:53:44
%S A356148 1,2,2,4,3,4,3,6,6,4,6,6,6,6,4,8,9,9,8,8,5,9,9,9,8,8,9,9,9,8,5,10,12,
%T A356148 13,12,12,12,10,12,12,12,6,10,12,12,13,12,12,12,12,10,12,10,12,13,12,
%U A356148 12,12,13,12,12,10,6,12,15,17,16,17,17,16,15,17,15
%N A356148 a(n) is the number of positive integers whose binary expansion appears as a substring in the binary expansion of n or its complement.
%C A356148 Leading 0's in binary expansions are ignored.
%H A356148 Rémy Sigrist, <a href="/A356148/b356148.txt">Table of n, a(n) for n = 1..8192</a>
%H A356148 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A356148 a(n) >= A122953(n).
%F A356148 a(2^k-1) = 2^k-1 for any k >= 0.
%F A356148 a(2^k) = A004277(k) for any k >= 0.
%e A356148 For n = 43:
%e A356148 - the binary expansion of 43 is "101011",
%e A356148 - it contains the positive numbers with binary expansions "1", "10", "11", "101", "1010", "1011", "10101", "101011",
%e A356148 - the complement of "101011" is "010100",
%e A356148 - it contains the positive numbers with binary expansions "1", "10", "100", "101", "1010", "10100",
%e A356148 - all in all, we have the following substrings: "1", "10", "11", "100", "101", "1010", "1011", "10100", "10101", "101011",
%e A356148 - so a(43) = 10.
%o A356148 (PARI) a(n) = { my (b=binary(n)); #setbinop((i,j) -> my (s=fromdigits(b[i..j], 2)); if (b[i], s, 2^(j-i+1)-1-s), [1..#b]) }
%o A356148 (Python)
%o A356148 def a(n):
%o A356148     N = n.bit_length()
%o A356148     c, s = ((1<<N)-1)^n, set()
%o A356148     for i in range(N):
%o A356148         for l in range(N-i):
%o A356148             mask = ((2<<l)-1) << i
%o A356148             s.add((mask&n) >> i)
%o A356148             s.add((mask&c) >> i)
%o A356148     return len(s - {0})
%o A356148 print([a(n) for n in range(1, 74)]) # _Michael S. Branicky_, Jul 28 2022
%Y A356148 Cf. A004277, A122953, A356149, A356150.
%K A356148 nonn,base
%O A356148 1,2
%A A356148 _Rémy Sigrist_, Jul 28 2022