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

2, 2, 0, 0, 1, 0, 1, 0, 3, 2, 1, 0, 1, 0, 17, 16, 1, 0, 1, 0, 3, 2, 1, 0, 5, 4, 5, 4, 1, 0, 1, 0, 5, 4, 9, 8, 1, 0, 9, 8, 1, 0, 1, 0, 3, 2, 1, 0, 5, 4, 9, 8, 1, 0, 73, 72, 3, 2, 1, 0, 1, 0, 65, 64, 3, 2, 1, 0, 3, 2, 1, 0, 1, 0, 5, 4, 3, 2, 1, 0, 3, 2, 1, 0, 43

Offset: 0

Author

Rémy Sigrist, Nov 23 2017

Keywords

• nonn
• base
• look

Comments

See A295609 for the corresponding prime numbers.

We can show that this sequence is well defined by using Dirichlet's theorem on arithmetic progressions.

a(n) = 0 iff n is prime.

For any n >= 0, n AND a(n) = 0 (where AND denotes the bitwise AND operator).

If a(n) = x + y with x AND y = 0, then a(n + x) = y.

This sequence has similarities with A007920: here we check n OR k, there we check n + k.

See A295520 for the XOR variant.

For any k > 0, a(2^(6*k)-1) >= 2^(6*k) (hence the sequence is unbounded).

Examples

			For n = 42, 42 OR 0 = 42 is not prime, 42 OR 1 = 43 is prime, hence a(42) = 1.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 0..8191
• Antti Karttunen, Data supplement: n, a(n) computed for n = 0..65537
• Rémy Sigrist, Scatterplot of the first 2^17 terms
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A003986, A007920, A295520, A295609.

Programs

Mathematica

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

PARI

avoid(n,i) = if (i, if (n%2, 2*avoid(n\2,i), 2*avoid(n\2,i\2)+(i%2)), 0) \\ (i+1)-th number k such that k AND n = 0
a(n) = for (i=0, oo, my (k=avoid(n,i)); if (isprime(n+k), return (k)))

Formula

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