A361191 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

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.

LINKS

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

Rémy Sigrist, C++ program

EXAMPLE

The first terms (at the bottom of the tree) alongside the corresponding sums are:

103

---------------------------------

23 112

----------------- -----------------

15 24 17 97

--------- --------- --------- ---------