cp's OEIS Frontend

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.

%I A352713 #19 Jun 24 2022 14:06:44
%S A352713 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,
%T A352713 17,40,19,72,21,104,22,128,23,160,25,68,26,100,27,192,28,34,29,224,30,
%U A352713 256,31,320,33,76,35,88,37,136,38,144,39,208,41,84,42,132,43
%N 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.
%C A352713 To build the sequence:
%C A352713 - we start with a(0) = 0, and then iteratively:
%C A352713 - let v be the last value, and u be the least value not yet in the sequence,
%C A352713 - if v AND u = 0, then the next value is u (AND denotes the bitwise AND operator),
%C A352713 - otherwise the next values are w and then u where w is chosen as small as possible.
%C A352713 This sequence is a variant of A109812 where we repeatedly force the least unseen value to appear as soon as possible.
%C A352713 By design, this is a permutation of the nonnegative integers (with inverse A352714).
%H A352713 Rémy Sigrist, <a href="/A352713/b352713.txt">Table of n, a(n) for n = 0..10000</a>
%H A352713 Rémy Sigrist, <a href="/A352713/a352713.png">Colored logarithmic scatterplot of the first 2^16 terms</a> (the color denotes the parity of n: blue for even, red for odd)
%H A352713 Rémy Sigrist, <a href="/A352713/a352713.gp.txt">PARI program</a>
%H A352713 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H A352713 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e A352713 The first terms are (stars correspond to "w" terms):
%e A352713   n   a(n)  bin(a(n))  w
%e A352713   --  ----  ---------  -
%e A352713    0     0          0
%e A352713    1     1          1
%e A352713    2     2         10
%e A352713    3     4        100  *
%e A352713    4     3         11
%e A352713    5     8       1000  *
%e A352713    6     5        101
%e A352713    7    16      10000  *
%e A352713    8     6        110
%e A352713    9    24      11000  *
%e A352713   10     7        111
%e A352713   11    32     100000  *
%e A352713   12     9       1001
%e A352713   13    20      10100  *
%e A352713   14    10       1010
%e A352713   15    36     100100  *
%o A352713 (PARI) See Links section.
%o A352713 (Python)
%o A352713 from math import gcd
%o A352713 from itertools import count, islice
%o A352713 def agen(): # generator of terms
%o A352713     aset, v, u = {0}, 0, 1; yield 0
%o A352713     for n in count(1):
%o A352713         if v&u != 0:
%o A352713             w = u + 1
%o A352713             while w in aset or v&w != 0 or w&u != 0: w += 1
%o A352713             aset.add(w); yield w
%o A352713         v = u; aset.add(v); yield v
%o A352713         while u in aset: u += 1
%o A352713 print(list(islice(agen(), 65))) # _Michael S. Branicky_, Jun 24 2022
%Y A352713 Cf. A109812, A352714 (inverse).
%K A352713 nonn,base
%O A352713 0,3
%A A352713 _Rémy Sigrist_, Mar 30 2022