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

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.

Links

Table of n, a(n) for n=1..67.

Index entries for sequences that are permutations of the natural numbers

Example

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

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

Prog

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

Crossrefs

Cf. A004443, A359947.

Sequence in context: A073672 A306230 A071065 * A328654 A035552 A339372

Adjacent sequences: A359943 A359944 A359945 * A359947 A359948 A359949

Keyword

nonn,base

Author

Rémy Sigrist, Jan 19 2023

Status

approved