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

Author

Rémy Sigrist, May 09 2020

Keywords

• nonn
• base

Comments

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

Examples

			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.
		

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

Crossrefs

See A334595 for a similar sequence.

Programs

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) }

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.