A295609 a(n) = least prime number p such that p AND n = n (where AND denotes the binary AND operator).

2, 3, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13, 31, 31, 17, 17, 19, 19, 23, 23, 23, 23, 29, 29, 31, 31, 29, 29, 31, 31, 37, 37, 43, 43, 37, 37, 47, 47, 41, 41, 43, 43, 47, 47, 47, 47, 53, 53, 59, 59, 53, 53, 127, 127, 59, 59, 59, 59, 61, 61, 127, 127, 67, 67

Offset: 0

Author

Rémy Sigrist, Nov 24 2017

Keywords

• nonn
• base

Comments

For any n > 0: gcd(A109613(n), A062383(n)) = 1, hence, by Dirichlet's theorem on arithmetic progressions, we have a prime number, say p, of the form A109613(n) + k * A062383(n) with k > 0; this prime number satisfies p AND n = n; also a(0) = 2, hence the sequence is well defined for any n >= 0.

a(n) = n iff n is prime.

Each prime number appears 2*k times in this sequence for some k > 0.

Examples

			a(42) = 42 + A295335(42) = 42 + 1 = 43.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..8192
• Rémy Sigrist, Scatterplot of the first 2^17 terms

Crossrefs

Cf. A062383, A109613, A295335.

Programs

Mathematica

Table[Block[{p = 2}, While[BitAnd[p, n] != n, p = NextPrime@ p]; p], {n, 0, 65}] (* 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 (n+k)))

Formula

a(n) = n + A295335(n).

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