login
A360363
Lexicographically earliest sequence of distinct positive integers such that the bitwise XOR of two distinct terms are all distinct.
3
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, 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
KEYWORD
nonn,base
AUTHOR
Rémy Sigrist, Feb 04 2023
STATUS
approved