A375487 a(n) is the number of integers k between 0 and n such that n AND k is a prime number (where AND denotes the bitwise AND operator).

0, 0, 1, 2, 0, 1, 2, 4, 0, 0, 4, 5, 0, 3, 2, 6, 0, 1, 8, 10, 0, 6, 4, 11, 0, 4, 4, 10, 0, 7, 2, 11, 0, 0, 16, 16, 0, 9, 8, 17, 0, 1, 8, 14, 0, 12, 4, 16, 0, 8, 8, 16, 0, 13, 4, 17, 0, 8, 4, 15, 0, 15, 2, 18, 0, 0, 32, 33, 0, 16, 16, 34, 0, 1, 16, 27, 0, 18, 8

Offset: 0

Author

Rémy Sigrist, Aug 17 2024

Keywords

• nonn
• base
• easy

Examples

			The first terms, alongside the corresponding k's, are:
  n   a(n)  k's
  --  ----  ------------------
   0     0  None
   1     0  None
   2     1  2
   3     2  2, 3
   4     0  None
   5     1  5
   6     2  2, 3
   7     4  2, 3, 5, 7
   8     0  None
   9     0  None
  10     4  2, 3, 6, 7
  11     5  2, 3, 6, 7, 11
  12     0  None
  13     3  5, 7, 13
  14     2  2, 3
  15     6  2, 3, 5, 7, 11, 13
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..8192
• Rémy Sigrist, Scatterplot of (n, k) such that 0 <= k <= n <= 1024 and n AND k is prime

Crossrefs

Cf. A000720, A102210, A117494, A375485 (XOR variant), A375486 (OR variant).

Programs

PARI

a(n) = sum(k = 0, n, isprime(bitand(n, k)))

Formula

a(n) = 0 iff n = 0 or n belongs to A102210.

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