login
A370790
Lexicographically earliest sequence of distinct nonnegative integers such that for any n >= 0, a(n) AND a(n+1) equals 0, a(n) or a(n+1) (where AND denotes the bitwise AND operator).
3
0, 1, 2, 3, 4, 5, 7, 6, 8, 9, 11, 10, 14, 12, 13, 15, 16, 17, 19, 18, 22, 20, 21, 23, 31, 24, 25, 27, 26, 30, 28, 29, 32, 33, 35, 34, 38, 36, 37, 39, 47, 40, 41, 43, 42, 46, 44, 45, 61, 48, 49, 51, 50, 54, 52, 53, 55, 63, 56, 57, 59, 58, 62, 60, 64, 65, 67, 66
OFFSET
0,3
COMMENTS
This sequence has connections with A109812 (as A109812(n) AND A109812(n+1) = 0) and with A303767 (as A303767(n) AND A303767(n+1) = A303767(n) or A303767(n+1)).
This sequence is a permutation of the nonnegative integers (with inverse A370791):
- 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.
FORMULA
Empirically:
- a(2^k) = 2^k for any k >= 0,
- a(n) AND a(n+1) = 0 iff n belongs to A000225,
- A070939(a(n)) = A070939(n) (the sequence preserves the binary length).
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 6
7 6 0
8 8 8
9 9 9
10 11 10
11 10 10
12 14 12
13 12 12
14 13 13
15 15 0
16 16 16
PROG
(PARI) See Links section.
CROSSREFS
Sequence in context: A100806 A102451 A370791 * A233280 A233279 A359752
KEYWORD
nonn,base
AUTHOR
Rémy Sigrist, Mar 02 2024
STATUS
approved