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,2

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).

Links

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

Rémy Sigrist, C++ program

Example

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

Prog

(C++) See Links section.
(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

Crossrefs

Cf. A000079, A011185, A346298, A360364.

Sequence in context: A189375 A262975 A062923 * A133464 A273731 A013914

Adjacent sequences: A360360 A360361 A360362 * A360364 A360365 A360366

Keyword

nonn,base

Author

Rémy Sigrist, Feb 04 2023

Status

approved