A352808 Lexicographically earliest sequence of distinct nonnegative integers such that for any n >= 0, a(n) AND a(floor(n/2)) = 0 (where AND denotes the bitwise AND operator).

0, 1, 2, 4, 5, 8, 3, 9, 10, 16, 6, 7, 12, 20, 18, 22, 17, 21, 11, 13, 24, 25, 32, 40, 19, 33, 34, 35, 36, 37, 41, 64, 14, 38, 42, 66, 48, 52, 50, 80, 39, 65, 68, 70, 15, 23, 67, 69, 44, 72, 26, 28, 29, 73, 76, 84, 27, 74, 82, 88, 86, 128, 30, 31, 49, 81, 89

Offset

0,3

Comments

This sequence has connections with A109812; each term (except the first) has no 1 bit in common with some prior term.

This sequence is a permutation of the natural numbers. [Proof: The first term divisible by a given power of 2, 2^k say, is 2^k itself, and for k >= 3, it is immediately followed by the smallest missing number. Since there are infinitely many powers of 2, every number will eventually appear. - N. J. A. Sloane, May 17 2022]

An alternative and equivalent definition: a(0)=0, a(1)=1. For k >= 1, a(2*k) and a(2*k+1) are the two smallest numbers not yet in the sequence whose binary expansions have no 1's in common with the binary expansion of a(k). - N. J. A. Sloane, May 17 2022

Links

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

Rémy Sigrist, C++ program

Index entries for sequences that are permutations of the natural numbers

Example

The initial terms a(n), alongside the binary expansions of a(n) and a(floor(n/2)), are:
  n   a(n)  bin(a(n))  bin(a(floor(n/2)))
  --  ----  ---------  ------------------
   0     0          0                   0
   1     1          1                   0
   2     2         10                   1
   3     4        100                   1
   4     5        101                  10
   5     8       1000                  10
   6     3         11                 100
   7     9       1001                 100
   8    10       1010                 101
   9    16      10000                 101
  10     6        110                1000
  11     7        111                1000
  12    12       1100                  11

Prog

(C++) See Links section.
(Python)
from itertools import count, islice
def agen(): # generator of terms
    alst = [0, 1]; aset = {0, 1}; yield from alst
    mink = 2
    for n in count(2):
        ahalf, k = alst[n//2], mink
        while k in aset or k&ahalf: k += 1
        alst.append(k); aset.add(k); yield k
        while mink in aset: mink += 1
print(list(islice(agen(), 67))) # Michael S. Branicky, May 17 2022

Crossrefs

Cf. A109812, A353731 (primes), A353732 (inverse), A354141 (powers of 2), A354142, A353733 (variant).

Sequence in context: A101410 A110991 A262942 * A076990 A330434 A330424

Adjacent sequences: A352805 A352806 A352807 * A352809 A352810 A352811

Keyword

nonn,look,base

Author

Rémy Sigrist, Apr 04 2022

Status

approved