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

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

Offset

0,3

Comments

This sequence is a permutation of the nonnegative integers (as it is injective and preserves the binary length); see A333777 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) with equality iff n = 0 or n is a power of 2.

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 0 1(0 1 0 1)
    1(1 0 1 0 1 0)
- the resulting binary representation is "1101010"
- and a(90) = 106.
The binary plot of the first terms is as follows (#'s denote 1's):
                                  ################################
                  ################ # #  ##    ####        ########
          ######## # #  ##    ####  ## # #  ## # #    #### # #  ##
      #### # #  ##  ## # #  ## # #    #### # #  ##  ## # #  ## # #
    ## # #  ## # #    #### # #  ##        ######## # #  ##    ####
   # #  ##    ####        ########                ################
            1         2         3         4         5         6
  0123456789012345678901234567890123456789012345678901234567890123

Prog

(PARI) a(n, base=2) = { my (d=digits(n, base), t=[]); forstep (k=#d, 1, -1, if (d[k], t=Vecrev(t)); t=concat(d[k], t)); fromdigits(t, base); }

Crossrefs

See A333692 for a similar sequence.

Cf. A000120, A330081, A333777 (inverse), A333778 (fixed points).

Sequence in context: A333777 A306869 A139708 * A305410 A059893 A331274

Adjacent sequences: A333773 A333774 A333775 * A333777 A333778 A333779

Keyword

nonn,base

Author

Rémy Sigrist, Apr 05 2020

Status

approved