login
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).
3
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.
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
KEYWORD
nonn,base
AUTHOR
Rémy Sigrist, Mar 02 2024
STATUS
approved