A367262 Lexicographically earliest sequence of distinct nonnegative integers such that the values a(0) XOR ... XOR a(k) (for some k >= 0) are all distinct (where XOR denotes the bitwise XOR operator).

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

Offset: 0

Author

Rémy Sigrist, Nov 11 2023

Keywords

• nonn
• base

Comments

This sequence is a variant of A333400; here we combine initial terms with the XOR operator, there with the addition.

This sequence is well defined; after some initial terms we can extend the sequence with a power of 2 greater that any prior term or even a smaller value.

This sequence is a permutation of the nonnegative integers (with inverse A367263):

- for any k >= 0, the least value >= 2^k is precisely 2^k,

- all powers of 2 appear in the sequence,

- after a power of 2, if the least value not yet in the sequence is less than this power of 2, then this value will be the next term.

Examples

			The first terms are:
  n   a(n)  a(0) XOR ... XOR a(n)
  --  ----  ---------------------
   0     0                      0
   1     1                      1
   2     2                      3
   3     4                      7
   4     3                      4
   5     6                      2
   6     7                      5
   7     8                     13
   8     5                      8
   9    14                      6
  10     9                     15
  11    16                     31
  12    10                     21
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..10000
• Rémy Sigrist, C++ program
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A333400, A346298, A367263 (inverse), A367264.