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

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

Formula

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

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

Example

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

Prog

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

Crossrefs

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

Sequence in context: A354773 A368724 A304784 * A354665 A131644 A115346

Adjacent sequences: A375484 A375485 A375486 * A375488 A375489 A375490

Keyword

nonn,base,easy

Author

Rémy Sigrist, Aug 17 2024

Status

approved