login
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.
1
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,1
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'.
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.
EXAMPLE
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.
PROG
(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)))) }
CROSSREFS
KEYWORD
nonn
AUTHOR
Rémy Sigrist, Mar 04 2023
STATUS
approved