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

Author

Rémy Sigrist, Apr 04 2020

Keywords

• nonn
• base

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.

Examples

			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.
		

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

Crossrefs

See A333776 for a similar sequence.

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

Programs

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

Formula

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

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

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