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

Author

Rémy Sigrist, Dec 01 2019

Keywords

• nonn
• base

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.

Examples

			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.
		

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 A330081 for a similar sequence.

Cf. A003558, A194959, A330091 (inverse).

Programs

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

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