A380856 In the binary expansion of n, arrange bits row-wise in a binary tree which is complete except for the last row and then read those bits in pre-order.

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

Offset: 0

Author

Darío Clavijo, Feb 06 2025

Keywords

• nonn
• look
• base

Comments

The formed tree is a max-heap when n is in A335040, also is strict if n is in A053738 and not strict if n is in A053754.

The re-ordering of the bits depends only on the bit length of n (cf. A379905), and the two most significant bits are always fixed.

If the remaining bits are all 0's or all 1's then re-ordering them is no change so that fixed points a(n) = n include n = 2^k or 2^k-1.

Examples

			For n = 65537, its binary expansion 10000000000000001 is arranged by rows in the following tree
            ______1______
           /             \
        __0__           __0__
       /     \         /     \
      0       0       0       0
     / \     / \     / \     / \
    0   0   0   0   0   0   0   0
   / \
  0   1
Reading this in pre-order is binary 10000100000000000 so that a(65537) = 67584.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..32768
• Wikipedia, Heap (data structure)
• Wikipedia, Tree traversal: Pre-order
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A000079, A000225, A007283, A053738, A053754, A335040, A379905.

Cf. A378496 (inverse permutation).

Programs

Maple

a:= proc(n) uses Bits; local b, l; b, l:= i->
      `if`(i>nops(l), [], [b(2*i+1)[], b(2*i)[], l[-i]]),
       Split(n); Join(b(1))
    end:
seq(a(n), n=0..68);  # Alois P. Heinz, Feb 06 2025

Mathematica

a[n_Integer] := Module[{res = {}, data, len},
  data = IntegerDigits[n, 2];
  len = Length[data];
  Which[
   MemberQ[{0, 1, 2}, n], n,
   True,
   DepthFirstScan[TreeGraph[Table[Floor[j/2] -> j, {j, 2, len}]],
    1, {"PrevisitVertex" -> (AppendTo[res, #] &)}];
   FromDigits[data[[res]], 2]]]; a /@ Range[0, 68]
 (* Shenghui Yang, Feb 14 2025 *)

Python

from binarytree import Node, build
a = lambda n: int("".join([node.value for node in build(bin(n)[2:]).preorder]),2)
print([a(n) for n in range(1, 69)])