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

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

Offset: 1

Author

Rémy Sigrist, Nov 21 2020

Keywords

• nonn
• base

Comments

By Dirichlet's theorem on arithmetic progressions, we can always extend the sequence: say a(n) < 2^k:

- if a(n) is odd: a(n) and 2^k are coprime and there are infinitely many prime numbers of the form a(n) + m*2^k = a(n) XOR m*2^k, and we can extend the sequence,

- if a(n) is even: a(n)+1 and 2^k are coprime and there are infinitely many prime numbers of the form a(n)+1 + m*2^k = a(n) XOR (1+m*2^k), and we can extend the sequence.

Examples

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

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..10000

Crossrefs

See A337013 for the corresponding prime numbers.

See A308334 for similar sequences.

Programs

PARI

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