A334727 Binary interpretation of the left diagonal of the XOR-triangle with first row generated from the binary expansion of n, with most significant bit given by first row.

0, 1, 3, 2, 7, 6, 5, 4, 15, 14, 12, 13, 10, 11, 9, 8, 31, 30, 29, 28, 25, 24, 27, 26, 21, 20, 23, 22, 19, 18, 17, 16, 63, 62, 60, 61, 59, 58, 56, 57, 51, 50, 48, 49, 55, 54, 52, 53, 42, 43, 41, 40, 46, 47, 45, 44, 38, 39, 37, 36, 34, 35, 33, 32, 127, 126, 125

Offset

0,3

Comments

This sequence is a self-inverse permutation of the nonnegative numbers, with only two fixed points: a(0) = 0 and a(1) = 1.

Links

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

Index entries for sequences related to binary expansion of n

Index entries for sequences related to XOR-triangles

Index entries for sequences that are permutations of the natural numbers

Formula

a(floor(n/2)) = floor(a(n)/2).

abs(a(2*n+1) - a(2*n)) = 1.

a(2^k) = 2^(k+1) - 1 for any k >= 0.

a(2^k-1) = 2^(k-1) for any k > 0.

Example

For n = 42:
- the binary expansion of 42 is "101010",
- the corresponding XOR-triangle is:
    1 0 1 0 1 0
     1 1 1 1 1
      0 0 0 0
       0 0 0
        0 0
         0
- the bits on the left diagonal are: 1, 1, 0, 0, 0, 0,
- so a(42) = 2^5 + 2^4 = 48.

Prog

(PARI) a(n) = { my (v=0); forstep (x=#binary(n)-1, 0, -1, if (bittest(n, x), v+=2^x; ); n=bitxor(n, n\2)); return (v) }

Crossrefs

See A334595 for a similar sequence.

Sequence in context: A071574 A341336 A276344 * A341335 A276343 A054429

Adjacent sequences: A334724 A334725 A334726 * A334728 A334729 A334730

Keyword

nonn,base

Author

Rémy Sigrist, May 09 2020

Status

approved