A359946 Lexicographically earliest sequence of distinct positive integers such that for any n > 0, n XOR a(n) is a prime number (where XOR denotes the bitwise XOR operator).

2, 1, 4, 3, 6, 5, 10, 11, 12, 7, 8, 9, 14, 13, 16, 15, 18, 17, 20, 19, 22, 21, 26, 27, 28, 23, 24, 25, 30, 29, 34, 35, 36, 31, 32, 33, 38, 37, 42, 43, 44, 39, 40, 41, 46, 45, 48, 47, 50, 49, 52, 51, 54, 53, 58, 59, 60, 55, 56, 57, 62, 61, 64, 63, 66, 65, 68

Offset: 1

Author

Rémy Sigrist, Jan 19 2023

Keywords

• nonn
• base

Comments

This sequence is a self-inverse permutation of the positive integers.

See A359947 for the corresponding prime numbers.

When considering nonnegative integers instead of positive integers, we obtain A004443.

Examples

			The first terms, alongside n XOR a(n), are:
  n   a(n)  n XOR a(n)
  --  ----  ----------
   1     2           3
   2     1           3
   3     4           7
   4     3           7
   5     6           3
   6     5           3
   7    10          13
   8    11           3
   9    12           5
  10     7          13
  11     8           3
  12     9           5
		

Links

• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A004443, A359947.

Programs

Mathematica

nn = 2^10; c[] := False; a[1] = 2; c[2] = True; u = 1; Do[k = u; While[Nand[! c[k], PrimeQ@ BitXor[n, k]], k++]; Set[{a[n], c[k]}, {k, True}]; If[k == u, While[c[u], u++]], {n, 2, nn}]; Array[a, nn] (* _Michael De Vlieger, Jan 21 2023 *)

PARI

{ s = 0; for (n=1, 67, for (v=1, oo, if (!bittest(s, v) && isprime(bitxor(n, v)), print1 (v", "); s += 2^v; break))) }