A295520 a(n) is the least k >= 0 such that n XOR k is prime (where XOR denotes the bitwise XOR operator).

2, 2, 0, 0, 1, 0, 1, 0, 3, 2, 1, 0, 1, 0, 3, 2, 1, 0, 1, 0, 3, 2, 1, 0, 5, 4, 5, 4, 1, 0, 1, 0, 5, 4, 7, 6, 1, 0, 3, 2, 1, 0, 1, 0, 3, 2, 1, 0, 5, 4, 7, 6, 1, 0, 3, 2, 3, 2, 1, 0, 1, 0, 3, 2, 3, 2, 1, 0, 3, 2, 1, 0, 1, 0, 3, 2, 3, 2, 1, 0, 3, 2, 1, 0, 7, 6, 5

Offset: 0

Author

Rémy Sigrist, Nov 23 2017

Keywords

• nonn
• base

Comments

a(n) = n iff n is prime.

For any n >= 0, a(n) <= A295335(n).

See A295335 for the OR variant.

Examples

			For n = 44:
- 44 XOR 0 = 44 is not prime,
- 44 XOR 1 = 45 is not prime,
- 44 XOR 2 = 46 is not prime,
- 44 XOR 3 = 47 is prime,
- hence a(44) = 3.
		

Links

• Robert Israel, Table of n, a(n) for n = 0..10000
• Rémy Sigrist, Scatterplot of (x, y) such that x XOR y is prime and x, y < 1024

Crossrefs

Cf. A295335.

Programs

Maple

f:= proc(n) local k;
  for k from 0 do if isprime(Bits:-Xor(k,n)) then return k fi od
end proc:
map(f, [$0..200]); # Robert Israel, Nov 27 2017

Mathematica

Table[Block[{k = 0}, While[! PrimeQ@ BitXor[k, n], k++]; k], {n, 0, 104}] (* Michael De Vlieger, Nov 26 2017 *)

PARI

a(n) = for (k=0, oo, if (isprime(bitxor(n,k)), return (k)))

Python

from itertools import count
from sympy import isprime
def A295520(n): return next(k for k in count(0) if isprime(n^k)) # Chai Wah Wu, Aug 23 2023

Formula

Empirically, for any k > 1, a(2*k+1) = a(2*k)-1.