cp's OEIS Frontend

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

%I A295335 #31 Mar 31 2021 10:49:29
%S A295335 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 A295335 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 A295335 2,1,0,3,2,1,0,1,0,5,4,3,2,1,0,3,2,1,0,43
%N A295335 a(n) = least k >= 0 such that n OR k is prime (where OR denotes the bitwise OR operator).
%C A295335 See A295609 for the corresponding prime numbers.
%C A295335 We can show that this sequence is well defined by using Dirichlet's theorem on arithmetic progressions.
%C A295335 a(n) = 0 iff n is prime.
%C A295335 For any n >= 0, n AND a(n) = 0 (where AND denotes the bitwise AND operator).
%C A295335 If a(n) = x + y with x AND y = 0, then a(n + x) = y.
%C A295335 This sequence has similarities with A007920: here we check n OR k, there we check n + k.
%C A295335 See A295520 for the XOR variant.
%C A295335 For any k > 0, a(2^(6*k)-1) >= 2^(6*k) (hence the sequence is unbounded).
%H A295335 Antti Karttunen, <a href="/A295335/b295335.txt">Table of n, a(n) for n = 0..8191</a>
%H A295335 Antti Karttunen, <a href="/A295335/a295335.txt">Data supplement: n, a(n) computed for n = 0..65537</a>
%H A295335 Rémy Sigrist, <a href="/A295335/a295335.png">Scatterplot of the first 2^17 terms</a>
%H A295335 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A295335 For any k > 1, a(2*k+1) = a(2*k)-1.
%e A295335 For n = 42, 42 OR 0 = 42 is not prime, 42 OR 1 = 43 is prime, hence a(42) = 1.
%t A295335 Table[Block[{k = 0}, While[! PrimeQ@ BitOr[k, n], k++]; k], {n, 0, 84}] (* _Michael De Vlieger_, Nov 26 2017 *)
%o A295335 (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 A295335 a(n) = for (i=0, oo, my (k=avoid(n,i)); if (isprime(n+k), return (k)))
%Y A295335 Cf. A003986, A007920, A295520, A295609.
%K A295335 nonn,base,look
%O A295335 0,1
%A A295335 _Rémy Sigrist_, Nov 23 2017