A337242 a(n) is the greatest number m not yet in the sequence such that the binary expansions of m and of n have the same run lengths (up to order but with multiplicity).

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

Offset: 0

Author

Rémy Sigrist, Aug 21 2020

Keywords

• nonn
• look
• base

Comments

This sequence has similarities with A331274; here we consider run lengths in binary expansions, there binary digits.

This sequence is a self-inverse permutation of the nonnegative numbers.

This sequence preserves the number of binary digits (A070939) and the number of runs in binary expansions (A005811).

This sequence has interesting graphical features (see Links section).

Examples

			For n = 7280:
- 7280 has binary expansion "1110001110000",
- the corresponding run lengths are: {3, 3, 3, 4},
- there are four numbers k with the same multiset of run lengths:
    k     bin(k)           run lengths
    ----  ---------------  -----------
    7224  "1110000111000"  {3, 4, 3, 3}
    7280  "1110001110000"  {3, 3, 3, 4}
    7288  "1110001111000"  {3, 3, 4, 3}
    7736  "1111000111000"  {4, 3, 3, 3}
- so a(7224) = 7736,
     a(7280) = 7288,
     a(7288) = 7280,
     a(7736) = 7224.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..8191
• Rémy Sigrist, Scatterplot of the first 2^20 terms
• Rémy Sigrist, Scatterplot of (n-2^19, a(n)-2^19) for n = 2^19..2^20-1
• Rémy Sigrist, PARI program for A337242
• Index entries for sequences related to binary expansion of n
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A005811, A070939, A101211, A331274, A335834, A335835.

Programs

Mathematica

Nest[Function[{a, m}, Append[a, SelectFirst[m, FreeQ[a, #] &]]] @@ {#1, Sort[Map[FromDigits[Join @@ MapIndexed[ConstantArray[Boole[OddQ@ First[#2]], #1] &, #], 2] &, Permutations[Length /@ Split@ IntegerDigits[#2, 2]]], Greater]} & @@ {#, Length@ #} &, {0}, 66] (* Michael De Vlieger, Aug 22 2020 *)

PARI

See Links section.

Formula

a(2^k-1) = 2^k-1 for any k >= 0.