A370793 Lexicographically earliest sequence of distinct nonnegative integers such that for any n >= 0, a(n) AND a(n+1) equals 0 or a(n) (where AND denotes the bitwise AND operator).

0, 1, 2, 3, 4, 5, 7, 8, 6, 9, 11, 15, 16, 10, 14, 17, 12, 13, 18, 19, 23, 31, 32, 20, 21, 29, 34, 24, 25, 27, 36, 26, 30, 33, 22, 40, 41, 43, 47, 63, 64, 28, 35, 39, 55, 72, 37, 45, 61, 66, 44, 46, 62, 65, 38, 54, 73, 48, 49, 51, 59, 68, 42, 58, 69, 50, 76, 77

Offset

0,3

Comments

This sequence is a permutation of the nonnegative integers (with inverse A370794):- we can always extend the sequence with a power of 2 greater than any prior term,

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

- every power of 2 appears in the sequence, in ascending order,

- if a(n) = 2^k and the least value not in the sequence at this point, say v, satisfies v < 2^k, then a(n+1) = v, and eventually every nonnegative integer will appear in the sequence.

Links

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

Rémy Sigrist, Scatterplot of the first 500000 terms

Rémy Sigrist, C++ program

Rémy Sigrist, C++ program (faster)

Index entries for sequences that are permutations of the natural numbers

Example

The first terms, alongside the bitwise AND of consecutive terms, are:
  n   a(n)  a(n) AND a(n+1)
  --  ----  ---------------
   0     0                0
   1     1                0
   2     2                2
   3     3                0
   4     4                4
   5     5                5
   6     7                0
   7     8                0
   8     6                0
   9     9                9
  10    11               11
  11    15                0
  12    16                0

Prog

(C++) See Links section.

Crossrefs

See and A109812, A303767 and A370790 for similar sequences.

Cf. A370794 (inverse).

Sequence in context: A295087 A306010 A162375 * A334100 A194068 A194062

Adjacent sequences: A370790 A370791 A370792 * A370794 A370795 A370796

Keyword

nonn,base

Author

Rémy Sigrist, Mar 02 2024

Status

approved