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

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, 26, 25, 28, 29, 31, 1, 18, 19, 28, 21, 30, 31, 36, 25, 34, 35, 40, 37, 42, 43, 46, 33, 42, 43, 48, 45, 50, 51, 54, 49, 54, 55, 58, 57, 60, 61, 63, 1, 34, 35, 52, 37

Offset: 0

Author

Rémy Sigrist, Apr 09 2022

Keywords

• nonn
• base

Comments

See A353293 for the corresponding k's.

Examples

			For n = 10:
- we have:
      k   10 AND k
      --  --------
       1         0
       2         2
       3         2
       4         0
       5         0
       6         2
       7         2
       8         8
       9         8
      10        10
- so a(10) = #{2, 3, 6, 7, 8, 9, 10} = 7.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..8192
• Index entries for sequences related to binary expansion of n

Crossrefs

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

Programs

PARI

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

Formula

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

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

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

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