A372129 Lexicographically earliest sequence of distinct nonnegative integers such that for any n >= 0, the binary expansions of a(n), a(2*n+1) and a(2*n+2) have distinct 1's.

0, 1, 2, 4, 8, 5, 16, 3, 24, 6, 17, 10, 32, 7, 40, 12, 48, 33, 64, 9, 80, 14, 96, 20, 65, 11, 68, 56, 128, 18, 69, 19, 160, 13, 66, 22, 72, 15, 144, 34, 84, 35, 132, 49, 192, 21, 130, 41, 194, 26, 36, 52, 256, 25, 162, 67, 260, 23, 104, 37, 136, 42, 272, 44

Offset

0,3

Comments

This sequence is a permutation of the nonnegative integers with inverse A372131:

- for any k >= 0, the first term >= 2^k is precisely 2^k,

- all powers of 2 appear in the sequence, in increasing order,

- for any v >= 0, every power of 2 that doesn't appear in the binary expansion of v provides an opportunity to select v later, and eventually v will appear in the sequence.

Links

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

Rémy Sigrist, PARI program

Index entries for sequences that are permutations of the natural numbers

Formula

a(n) AND a(2*n+1) = a(n) AND a(2*n+2) = a(2*n+1) AND a(2*n+2) = 0 for any n >= 0 (where AND denotes the bitwise AND operator).

Example

The first terms, arranged alongside a binary tree where siblings have distinct binary 1's and parent and children have distinct binary 1's, are:
                |
        .-------0-------.
        |               |
    .---1---.       .---2---.
    |       |       |       |
  .-4-.   .-8-.   .-5-.   .16-.
  |   |   |   |   |   |   |   |
  3  24   6  17  10  32   7  40

Prog

(PARI) \\ See Links section.

Crossrefs

See A372030 for similar sequences.

Cf. A372130 (analog based on prime factors), A372131 (inverse), A372143 (analog with common 1 bit).

Sequence in context: A366304 A361191 A248573 * A369414 A125733 A333555

Adjacent sequences: A372126 A372127 A372128 * A372130 A372131 A372132

Keyword

nonn,base

Author

Rémy Sigrist, Apr 20 2024

Status

approved