A298847 Lexicographically earliest sequence of distinct positive terms such that, for any n > 0, the number of ones in the binary expansion of n equals one plus the number of zeros in the binary expansion of a(n).

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

Offset

1,2

Comments

In other words, for any n > 0, A000120(n) = 1 + A023416(a(n)).

This sequence is a self-inverse permutation of the natural numbers, with fixed points A031448.

We can build an analog of this sequence for any base b > 1:

- let s_b be the sum of digits in base b,

- in particular s_2 = A000120 and s_10 = A007953,

- let l_b be the number of digits in base b,

- in particular l_2 = A070939 and l_10 = A055642,

- let f_b be the lexicographically earliest sequence of distinct positive terms such that, for any n > 0, s_b(n) = 1 + (b-1) * l_b(a(n)) - s_b(a(n)),

- in particular, f_2 = a (this sequence),

- f_b is a self-inverse permutation of the natural numbers,

- l_b(n) = l_b(f_b(n)) for any n > 0,

- f_b(b^k) = b^(k+1) - 1 for any k >= 0,

- see also scatterplots of f_3 and f_10 in Links section.

Links

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

Rémy Sigrist, PARI program for A298847

Rémy Sigrist, Colored scatterplot of the first 2^16 - 1 terms (where the color is function of the Hamming weight of n)

Rémy Sigrist, Scatterplot of the first 3^9 - 1 terms of f_3

Rémy Sigrist, Scatterplot of the first 10^4 - 1 terms of f_10

Index entries for sequences that are permutations of the natural numbers

Formula

A070939(n) = A070939(a(n)) for any n > 0.

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

A000120(n) + A000120(a(n)) = 1 + A070939(n) for any n > 0.

Example

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

Prog

(PARI) See Links section.

Crossrefs

Cf. A000120, A007953, A023416, A031448, A055642, A070939.

Sequence in context: A303075 A286417 A303076 * A059894 A307544 A126314

Adjacent sequences: A298844 A298845 A298846 * A298848 A298849 A298850

Keyword

nonn,base

Author

Rémy Sigrist, Jan 27 2018

Status

approved