A372129 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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

| | | |