A316385 Lexicographically earliest sequence of distinct positive terms such that for any n > 0, a(n) AND a(2*n) = a(n) (where AND denotes the binary AND operator).

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

Offset: 1

Author

Rémy Sigrist, Jul 01 2018

Keywords

• nonn
• base

Comments

This sequence is a permutation of the natural numbers (as odd-indexed terms are not constrained); see A316472 for the inverse sequence.

In the binary plot of the sequence, if the pixel (x, y) is on, then the pixel (2*x, y) is on.

Examples

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

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..8191
• Rémy Sigrist, Colored scatterplot of the first 2^14-1 terms (where the color is function of the 2-adic valuation of n)
• Rémy Sigrist, PARI program for A316385
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A004755, A004761, A020989, A316472 (inverse).

Programs

PARI

See Links section.

Formula

Empirically:

- a(2*k) = A004755(a(k)) for any k > 0,

- a(2*k - 1) = A004761(k + 1) for any k > 0,

- a(n) = n iff n belongs to A020989.