A333692 Scan the binary representation of n from left to right; at each 1, reverse the bits to the left and including this 1. The resulting binary representation is that of a(n).

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

Offset

0,3

Comments

Leading zeros are ignored.

This sequence is a permutation of the nonnegative integers (as it is injective and preserves the binary length); see A333693 for the inverse.

We can devise a variant of this sequence for any fixed base b > 1, by performing a reversal at each nonzero digit in base b.

Links

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

Index entries for sequences related to binary expansion of n

Index entries for sequences that are permutations of the natural numbers

Formula

a(2*n) = 2*a(n).

a(2*n+1) = A030101(2*a(n)+1).

A000120(a(n)) = A000120(n).

Example

For n = 90:
- the binary representation of 90 is "1011010",
- this binary representation evolves as follows (parentheses indicate reversals):
   (1)0 1 1 0 1 0
   (1 0 1)1 0 1 0
   (1 1 0 1)0 1 0
   (1 0 1 0 1 1)0
- the resulting binary representation is "1010110"
- and a(90) = 86.

Prog

(PARI) a(n, base=2)={ my (b=digits(n, base), p=[]); for (k=1, #b, p=concat(p, b[k]); if (b[k], p=Vecrev(p))); fromdigits(p, base) }

Crossrefs

See A333776 for a similar sequence.

Cf. A000120, A030101, A333693 (inverse), A333762 (fixed points).

Sequence in context: A033621 A332808 A108548 * A333693 A322464 A057889

Adjacent sequences: A333689 A333690 A333691 * A333693 A333694 A333695

Keyword

nonn,base

Author

Rémy Sigrist, Apr 04 2020

Status

approved