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

Author

Rémy Sigrist, Jan 27 2018

Keywords

• nonn
• base

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.

Examples

			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
		

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

Crossrefs

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

Programs

PARI

See Links section.

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.