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

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).

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

Formula

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

Example

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

Mathematica

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

Prog

(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)))

Crossrefs

Cf. A003986, A007920, A295520, A295609.

Sequence in context: A298177 A298146 A295520 * A227838 A050605 A060571

Adjacent sequences: A295332 A295333 A295334 * A295336 A295337 A295338

Keyword

nonn,base,look

Author

Rémy Sigrist, Nov 23 2017

Status

approved