A295335 - OEIS

%I #31 Mar 31 2021 10:49:29

%S 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,

%T 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,

%U 2,1,0,3,2,1,0,1,0,5,4,3,2,1,0,3,2,1,0,43

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

%C See A295609 for the corresponding prime numbers.

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

%C a(n) = 0 iff n is prime.

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

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

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

%C See A295520 for the XOR variant.

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

%H Antti Karttunen, <a href="/A295335/b295335.txt">Table of n, a(n) for n = 0..8191</a>

%H Antti Karttunen, <a href="/A295335/a295335.txt">Data supplement: n, a(n) computed for n = 0..65537</a>

%H Rémy Sigrist, <a href="/A295335/a295335.png">Scatterplot of the first 2^17 terms</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

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

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

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

%o (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

%o a(n) = for (i=0, oo, my (k=avoid(n,i)); if (isprime(n+k), return (k)))

%Y Cf. A003986, A007920, A295520, A295609.

%K nonn,base,look

%O 0,1

%A _Rémy Sigrist_, Nov 23 2017