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

0, 0, 2, 2, 2, 2, 4, 4, 2, 2, 4, 4, 4, 4, 6, 6, 5, 5, 7, 7, 7, 7, 9, 9, 7, 7, 9, 9, 9, 9, 11, 11, 7, 7, 9, 9, 9, 9, 11, 11, 9, 9, 11, 11, 11, 11, 13, 13, 12, 12, 14, 14, 14, 14, 16, 16, 14, 14, 16, 16, 16, 16, 18, 18, 13, 13, 15, 15, 15, 15, 17, 17, 15, 15, 17

Offset

0,3

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 XOR k is prime

Formula

Empirically, if 2^k <= n < 2^(k+1) then a(n) + a(A054429(n)) only depends on k.

Example

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

Prog

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

Crossrefs

Cf. A054429, A375486 (OR variant), A375487 (AND variant).

Sequence in context: A125913 A122386 A051464 * A151565 A060632 A160407

Adjacent sequences: A375482 A375483 A375484 * A375486 A375487 A375488

Keyword

nonn,base,easy

Author

Rémy Sigrist, Aug 17 2024

Status

approved