A361191 Lexicographically earliest sequence of positive integers such that the sums SumXOR_{i = 1+k*2^e..(k+1)*2^e} a(i) with k, e >= 0 are all distinct (where SumXOR is the analog of summation under the binary XOR operation).

1, 2, 4, 8, 5, 11, 6, 16, 7, 10, 9, 21, 18, 32, 19, 64, 20, 33, 25, 49, 26, 34, 27, 65, 30, 35, 31, 66, 36, 71, 37, 105, 38, 67, 39, 108, 41, 68, 42, 128, 43, 69, 44, 116, 45, 70, 51, 176, 52, 72, 57, 129, 58, 73, 59, 118, 60, 78, 63, 130, 74, 132, 80, 256, 81

Offset: 1

Author

Rémy Sigrist, Mar 03 2023

Keywords

• nonn
• base

Comments

In other words, a(1), a(2), a(1) XOR a(2), a(3), a(4), a(3) XOR a(4), a(1) XOR a(2) XOR a(3) XOR a(4), a(5), a(6), a(5) XOR a(6), etc. are all distinct.

In particular, all terms are distinct (but not necessarily in increasing order).

We can arrange the terms of the sequence as the leaves of a perfect infinite binary tree, the sums with e > 0 corresponding to parent nodes; each node will contain a different value and all values will appear in the tree (if n = 2^m+1 for some m > 0, then a(n) will equal the least missing value so far in the tree).

This sequence is a variant of A361144 based on the bitwise XOR operator.

Examples

			The first terms (at the bottom of the tree) alongside the corresponding sums are:
                                 103
                  ---------------------------------
                 23                              112
          -----------------               -----------------
         15              24              17              97
      ---------       ---------       ---------       ---------
      3      12      14      22      13      28      50      83
    -----   -----   -----   -----   -----   -----   -----   -----
    1   2   4   8   5  11   6  16   7  10   9  21  18  32  19  64
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..8191
• Rémy Sigrist, C++ program

Crossrefs

Cf. A361144.