login
A352713
Lexicographically earliest sequence of distinct nonnegative integers such that the binary expansions of two consecutive terms have no common 1, and the least value not yet in the sequence appears as soon as possible.
4
0, 1, 2, 4, 3, 8, 5, 16, 6, 24, 7, 32, 9, 20, 10, 36, 11, 48, 12, 18, 13, 64, 14, 80, 15, 96, 17, 40, 19, 72, 21, 104, 22, 128, 23, 160, 25, 68, 26, 100, 27, 192, 28, 34, 29, 224, 30, 256, 31, 320, 33, 76, 35, 88, 37, 136, 38, 144, 39, 208, 41, 84, 42, 132, 43
OFFSET
0,3
COMMENTS
To build the sequence:
- we start with a(0) = 0, and then iteratively:
- let v be the last value, and u be the least value not yet in the sequence,
- if v AND u = 0, then the next value is u (AND denotes the bitwise AND operator),
- otherwise the next values are w and then u where w is chosen as small as possible.
This sequence is a variant of A109812 where we repeatedly force the least unseen value to appear as soon as possible.
By design, this is a permutation of the nonnegative integers (with inverse A352714).
EXAMPLE
The first terms are (stars correspond to "w" terms):
n a(n) bin(a(n)) w
-- ---- --------- -
0 0 0
1 1 1
2 2 10
3 4 100 *
4 3 11
5 8 1000 *
6 5 101
7 16 10000 *
8 6 110
9 24 11000 *
10 7 111
11 32 100000 *
12 9 1001
13 20 10100 *
14 10 1010
15 36 100100 *
PROG
(PARI) See Links section.
(Python)
from math import gcd
from itertools import count, islice
def agen(): # generator of terms
aset, v, u = {0}, 0, 1; yield 0
for n in count(1):
if v&u != 0:
w = u + 1
while w in aset or v&w != 0 or w&u != 0: w += 1
aset.add(w); yield w
v = u; aset.add(v); yield v
while u in aset: u += 1
print(list(islice(agen(), 65))) # Michael S. Branicky, Jun 24 2022
CROSSREFS
Cf. A109812, A352714 (inverse).
Sequence in context: A120242 A322864 A355436 * A054427 A363537 A232563
KEYWORD
nonn,base
AUTHOR
Rémy Sigrist, Mar 30 2022
STATUS
approved