

A354169


a(0) = 0, a(1) = 1, a(2) = 2; for k >= 2, given a(k), the sequence is extended by adjoining two terms: a(2*k1) = smallest m >= 0 not among a(0) .. a(k) such that {m, a(k), a(k+1), ..., a(2*k2)} are pairwise disjoint in binary, and a(2*k) = smallest m >= 0 not among a(0) .. a(k) such that {m, a(k), ..., a(2*k1)} are pairwise disjoint in binary.


21



0, 1, 2, 4, 8, 3, 16, 32, 64, 12, 128, 256, 512, 17, 1024, 34, 2048, 4096, 8192, 68, 16384, 136, 32768, 65536, 131072, 768, 262144, 524288, 1048576, 1025, 2097152, 18, 4194304, 2080, 8388608, 16777216, 33554432, 12288, 67108864, 134217728, 268435456, 16388
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

The paper by De Vlieger et al. (2022) calls this the "binary twoup sequence".
"Pairwise disjoint in binary" means no common 1bits in their binary representations.
A consequence of the definition, and also an equivalent definition, is that this is the lexicographically earliest infinite sequence of distinct nonnegative numbers with the property that the binary representation of a(n) is disjoint from (has no common 1's with) the binary representations of the following n terms.
An equivalent definition is that a(n) is the smallest nonnegative number that is disjoint (in its binary representation) from each of the previous floor(n/2) terms.
For the subsequence 0, 3, 12, 17, 34, ... of the terms that are not powers of 2 see A354680 and A354798.
All terms are the sum of at most two powers of 2 (see De Vlieger et al., 2022).  N. J. A. Sloane, Aug 29 2022


LINKS

Michael De Vlieger, Thomas Scheuerle, Rémy Sigrist, N. J. A. Sloane, and Walter Trump, The Binary TwoUp Sequence, arXiv:2209.04108 [math.CO], Sep 11 2022.
N. J. A. Sloane, Lefthand portion of rows 97135 of preceding table, showing columns 6796, rotated counterclockwise by 90 degrees. The red line in this table should be aligned with the red line between rows 135 and 136 in the preceding table. [This portion of the table was too wide to fit through the scanner.]


EXAMPLE

After a(2) = 2 = 10_2, a(3) must equal ?0?_2, and the smallest such number we have not seen is a(3) = 100_2 = 4, and a(4) must equal ?00?_2, and the smallest such number we have not seen is a(4) = 1000_2 = 8.


MATHEMATICA

nn = 42; c[_] = r = 0; m = 1; Array[Set[{a[#], c[#]}, {#, #}] &, 2, 0]; Do[k = SelectFirst[Union@ Map[Total, Rest@ Subsets[2^Reverse[Length[#]  Position[#, 1][[All, 1]]] &@ IntegerDigits[2^(r + 2)  m  1, 2]]], c[#] == 0 &]; Set[{a[n], c[k]}, {k, n}]; m += a[n]; If[And[IntegerQ[#], # > 0], m = a[#]] &[n/2]; If[And[EvenQ[k], PrimePowerQ[k], k > 2^r], r++], {n, 2, nn}]; Table[a[n], {n, 0, nn}] (* Michael De Vlieger, Jul 13 2022 *)


PROG

(PARI) See Links section.
(Python)
from itertools import count, islice
from collections import deque
from functools import reduce
from operator import or_
def A354169_gen(): # generator of terms
aset, aqueue, b, f = {0, 1, 2}, deque([2]), 2, False
yield from (0, 1, 2)
while True:
for k in count(1):
m, j, j2, r, s = 0, 0, 1, b, k
while r > 0:
r, q = divmod(r, 2)
if not q:
s, y = divmod(s, 2)
m += y*j2
j += 1
j2 *= 2
if s > 0:
m += s*2**b.bit_length()
if m not in aset:
yield m
aset.add(m)
aqueue.append(m)
if f: aqueue.popleft()
b = reduce(or_, aqueue)
f = not f
break


CROSSREFS

A355889 is a more efficient way to present this sequence.
Cf. A000120, A090252, A098550, A121216, A252867, A347113, A353708, A353712, A354680, A354767, A354798, A355150.


KEYWORD

nonn,base


AUTHOR



EXTENSIONS



STATUS

approved



