A360363 Lexicographically earliest sequence of distinct positive integers such that the bitwise XOR of two distinct terms are all distinct.

1, 2, 3, 4, 8, 12, 16, 32, 48, 64, 85, 106, 128, 150, 171, 216, 237, 247, 256, 279, 297, 452, 512, 537, 558, 594, 640, 803, 860, 997, 1024, 1051, 1069, 1115, 1169, 1333, 1345, 1620, 1866, 2048, 2077, 2086, 2159, 2257, 2363, 2446, 2737, 2860, 3212, 3335, 3761

Offset: 1

Author

Rémy Sigrist, Feb 04 2023

Keywords

• nonn
• base

Comments

This sequence is well defined as we can always extend it with a power of 2 not yet in the sequence.

This sequence contains all powers of 2 (A000079).

This sequence has similarities with A011185: here we combine terms with the bitwise XOR operator, there with the addition.

Every positive integer can be uniquely expressed as a(i) XOR a(j) with i < j (see A360364).

Examples

			The first terms are:
  n   a(n)  a(k) XOR a(n) (for k = 1..n-1)
  --  ----  ----------------------------------------------------------
   1     1  N/A
   2     2  3
   3     3  2, 1
   4     4  5, 6, 7
   5     8  9, 10, 11, 12
   6    12  13, 14, 15, 8, 4
   7    16  17, 18, 19, 20, 24, 28
   8    32  33, 34, 35, 36, 40, 44, 48
   9    48  49, 50, 51, 52, 56, 60, 32, 16
  10    64  65, 66, 67, 68, 72, 76, 80, 96, 112
  11    85  84, 87, 86, 81, 93, 89, 69, 117, 101, 21
  12   106  107, 104, 105, 110, 98, 102, 122, 74, 90, 42, 63
  13   128  129, 130, 131, 132, 136, 140, 144, 160, 176, 192, 213, 234
		

Links

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

Crossrefs

Cf. A000079, A011185, A346298, A360364.

Programs

Python

from itertools import islice
def agen(): # generator of terms
    aset, xset, k = set(), set(), 0
    while True:
        k += 1
        while any(k^an in xset for an in aset): k += 1
        yield k; xset.update(k^an for an in aset); aset.add(k)
print(list(islice(agen(), 51))) # Michael S. Branicky, Feb 05 2023