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,4

Comments

See A353293 for the corresponding k's.

Links

Rémy Sigrist, Table of n, a(n) for n = 0..8192

Index entries for sequences related to binary expansion of n

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.

Example

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.

Prog

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

Crossrefs

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

Sequence in context: A046070 A068399 A225407 * A183904 A105177 A050057

Adjacent sequences: A353289 A353290 A353291 * A353293 A353294 A353295

Keyword

nonn,base

Author

Rémy Sigrist, Apr 09 2022

Status

approved