A361198 Consider a perfect infinite binary tree with nodes labeled with distinct positive integers where n appears at level A082850(n) and each level is filled from left to right; a(n) is the sibling of n in this tree.

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

Offset: 1

Author

Rémy Sigrist, Mar 04 2023

Keywords

• nonn

Comments

This sequence is a self-inverse permutation of the positive integers with no fixed point.

We can build a similar tree from any sequence of positive integers where each value appears infinitely many times. The choice of A082850 is interesting as each parent node appears immediately after its second child; also, for each pair of nodes of the same level, say p and p', and each pair of nodes, c and c', where c has ancestor p and c' has ancestor p', and the relative position of p with respect to c is the same as for p' with respect to c', we have p - c = p' - c'.

Empirically: to compute a(n): replace the least significant nonzero digit in the skew-binary expansion of n, say d, by 3-d. - Rémy Sigrist, Mar 02 2025

Examples

			The perfect infinite binary tree starts as follows:
                                 31
                  ---------------------------------
                 15                              30
          -----------------               -----------------
          7              14              22              29
      ---------       ---------       ---------       ---------
      3       6      10      13      18      21      25      28
    -----   -----   -----   -----   -----   -----   -----   -----
    1   2   4   5   8   9  11  12  16  17  19  20  23  24  26  27
.
So a(1) = 2 and a(2) = 1, a(4) = 5 and a(5) = 4, etc.,
   a(3) = 6 and a(6) = 3, a(10) = 13 and a(13) = 10, etc.,
   a(7) = 14 and a(14) = 7, a(22) = 29 and a(29) = 22,
   a(15) = 30 and a(30) = 15.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..8190
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A082850, A101925, A126646, A308187.

Programs

PARI

a(n) = { my (n0 = n); for (h = 2, oo, if (n < 2^h-1, while (1, my (w=2^h-- - 1); if (n == w, return (n0 - n + 2*w), n == 2*w, return (n0 - n + w), n > w, n -= w)))) }

Formula

a(A101925(2*n)) = A101925(2*n + 1).

a(A101925(2*n + 1)) = A101925(2*n).

A082850(a(n)) = A082850(n).

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

abs(a(n) - n) = 2^A082850(n) - 1 (belongs to A126646).

Apparently, a(n) < n iff A308187(n+1) = 1.