A340250 Lexicographically earliest sequence of distinct nonnegative terms such that for any n >= 0, a(n+1) is obtained by inverting the leftmost binary digit (which is not a leading zero) in a(n) or if this is not possible by inverting the rightmost leading binary zero in a(n).

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

Offset

0,3

Comments

This sequence has similarities with A003188, where we invert the rightmost possible binary digit.

This sequence appears to be a permutation of the nonnegative integers.

Links

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

Rémy Sigrist, PARI program for A340250

Rémy Sigrist, Binary plot of the sequence for n = 0..256

Formula

a(n) = A053645(A059894(2*A003188(n))) - A030301(n)*(-1)^A086694(n-1) for n > 1. - Mikhail Kurkov, Sep 30 2023 [verification needed]

Example

The first terms, alongside their binary representation, are:
  n   a(n)  bin(a(n))
  --  ----  ---------
   0     0          0
   1     1          1
   2     3         11
   3     2         10
   4     6        110
   5     4        100
   6     5        101
   7     7        111
   8    15       1111
   9    11       1011
  10     9       1001
  11    13       1101
  12    12       1100
  13     8       1000
  14    10       1010
  15    14       1110

Prog

(PARI) \\ See Links section.
(PARI) b1(n) = my(A = binary(n)); fromdigits(concat(1, Vecrev(vector(#A - 1, i, 1 - A[i + 1]))), 2)
a(n) = if(n < 2, n, my(L = logint(n, 2)); b1(2 * bitxor(n, n >> 1)) - 2 ^ (L + 1) - if(L % 2, (-1)^(n < 3 * 2 ^ (L - 1)))) \\ Mikhail Kurkov, Sep 30 2023 [verification needed]

Crossrefs

Cf. A003188, A340251, A340253 (ternary analog), A340254 (decimal analog), A340255 (factorial base analog), A340256 (primorial base analog).

Sequence in context: A254054 A303767 A163252 * A303773 A303769 A303775

Adjacent sequences: A340247 A340248 A340249 * A340251 A340252 A340253

Keyword

nonn,base,changed

Author

Rémy Sigrist, Jan 02 2021

Status

approved