A354141 -id:A354141 - cp's OEIS frontend

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

Rémy Sigrist, Apr 04 2022

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

			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

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

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

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

cp's OEIS Frontend

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).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python