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,3

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

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

Formula

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

Example

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.

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

Prog

(PARI) See Links section.

Crossrefs

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

Sequence in context: A336963 A175949 A166404 * A371343 A166166 A106452

Adjacent sequences: A337239 A337240 A337241 * A337243 A337244 A337245

Keyword

nonn,look,base

Author

Rémy Sigrist, Aug 21 2020

Status

approved