A353292 - OEIS

%I #11 Apr 11 2022 16:34:24

%S 0,1,1,3,1,4,5,7,1,6,7,10,9,12,13,15,1,10,11,16,13,18,19,22,17,22,23,

%T 26,25,28,29,31,1,18,19,28,21,30,31,36,25,34,35,40,37,42,43,46,33,42,

%U 43,48,45,50,51,54,49,54,55,58,57,60,61,63,1,34,35,52,37

%N a(n) is the number of positive integers k <= n that have at least one common 1-bit with n.

%C See A353293 for the corresponding k's.

%H Rémy Sigrist, <a href="/A353292/b353292.txt">Table of n, a(n) for n = 0..8192</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F a(n) = n - A115378(n) for any n > 0.

%F a(n) = A062050(n) + A088512(n) * A080100(n) for any n > 0.

%F a(2^k) = 1 for any k >= 0.

%F a(2^k - 1) = 2^k - 1 for any k >= 0.

%e For n = 10:

%e - we have:

%e       k   10 AND k

%e       --  --------

%e        1         0

%e        2         2

%e        3         2

%e        4         0

%e        5         0

%e        6         2

%e        7         2

%e        8         8

%e        9         8

%e       10        10

%e - so a(10) = #{2, 3, 6, 7, 8, 9, 10} = 7.

%o (PARI) a(n) = { my (h=hammingweight(n), w=#binary(n)); n-2^(w-1)+1 + (2^(h-1)-1)*2^(w-h) }

%Y Cf. A062050, A080100, A088512, A115378, A353293.

%K nonn,base

%O 0,4

%A _Rémy Sigrist_, Apr 09 2022