A329303 If the run lengths in binary expansion of n are (r(1), ..., r(w)), then the run lengths in binary expansion of a(n) are (r(1), r(3), r(5), ..., r(6), r(4), r(2)).

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

Offset

0,3

Comments

This sequence is a permutation of the nonnegative integers that preserves the binary length as well as the number of runs. See A330091 for the inverse.

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

If n has w binary runs, then a^A003558(w-1)(n) = n (where a^k denotes the k-th iterate of the sequence).

Example

For n = 19999:
- the binary representation of 19999 is "100111000011111",
- the corresponding run lengths are (1, 2, 3, 4, 5),
- hence the run lengths of a(n) are (1, 3, 5, 4, 2),
- and its binary representation is "100011111000011",
- so a(n) = 18371.

Prog

(PARI) torl(n) = { my (rr=[]); while (n, my (r=valuation(n+(n%2), 2)); rr = concat(r, rr); n\=2^r); rr }
shuffle(v) = { my (w=vector(#v), o=0, e=#v+1); for (k=1, #v, w[if (k%2, o++, e--)]=v[k]); w }
fromrl(rr) = { my (v=0); for (k=1, #rr, v = (v+(k%2))*2^rr[k]-(k%2)); v }
a(n) = fromrl(shuffle(torl(n)))

Crossrefs

See A330081 for a similar sequence.

Cf. A003558, A194959, A330091 (inverse).

Sequence in context: A361513 A255004 A257728 * A330091 A175948 A348268

Adjacent sequences: A329300 A329301 A329302 * A329304 A329305 A329306

Keyword

nonn,base

Author

Rémy Sigrist, Dec 01 2019

Status

approved