A324556 a(n) is the image of n obtained by a transformation on binary trees (see comments).

0, 1, 3, 2, 7, 5, 8, 4, 6, 11, 17, 9, 128, 32, 256, 16, 15, 10, 35, 19, 257, 65, 513, 33, 64, 2048, 131072, 512, 340282366920938463463374607431768211456, 4294967296, 115792089237316195423570985008687907853269984665640564039457584007913129639936, 65536, 13, 23

Offset

0,3

Comments

Let f(n) be the binary tree built as follows: create a root with value n and recursively apply the rule {if the value v of a node is not 0, write v in base 2, create a left child with value v minus its leading 1, create a right child with value the number of 0's that immediately followed the leading 1 in v}. The function f is a bijection; let g be its inverse; let r denote the reflection operator on binary trees (i.e., starting from the root, r recursively swaps left and right children). By definition a(n) = g(r(f(n))).

To better illustrate f, one can use an infinite hierarchic tree created as follows: create root node 0; for all i >= 0, for all j ranging from 0 to 2^i-1, create node j+2^i and append it to the list of children of j (see link). Every n >= 0 appears exactly once in this hierarchy. If n > 0, n can be referred to as child index c of node p, noted p.c, where both c and p are >= 0. Applying recursively to p and c the same reasoning leads to a syntactic construct made of zeros, dots and parentheses, structurally equivalent to the binary tree f(n).

Links

Table of n, a(n) for n=0..33.

Luc Rousseau, Helper hierarchic tree of the numbers from 0 to 31

Formula

a(a(n)) = n.

a(n) = n iff n is in A324557.

Example

11 is '1011' in binary, which is a one, followed by 1 zero, followed by '11' = 3. Then, 11 can be represented by the partial decomposition tree:
         11
         / \
        3   1
Pursuing the decomposition process yields the complete decomposition tree:
         11
         / \
        /   \
       /     \
      3       1
     / \     / \
    1   0   0   0
   / \
  0   0
Erase the numerical values other than 0:
          .
         / \
        /   \
       /     \
      .       .
     / \     / \
    .   0   0   0
   / \
  0   0
Apply reflection operator:
          .
         / \
        /   \
       /     \
      .       .
     / \     / \
    0   0   0   .
               / \
              0   0
Compute new numerical values from the leaves up:
          9
         / \
        /   \
       /     \
      1       2
     / \     / \
    0   0   0   1
               / \
              0   0
The root node has value 9, so a(11) = 9.

Mathematica

f[0] = {};
f[n_] := f /@ {FromDigits[#, 2], First@FirstPosition[#, 1, {Length@# + 1}] - 1} &@ Rest@IntegerDigits[n, 2];
g[{}] = 0;
g[{l_, r_}] := FromDigits[Join[{1}, ConstantArray[0, g[r]], If[# == 0, {}, IntegerDigits[#, 2]] &[g[l]]], 2];
rev[{}] = {};
rev[{l_, r_}] := {rev@r, rev@l};
Table[g[rev[f[n]]], {n, 40}]
(* Andrey Zabolotskiy, May 20 2019; requires Mathematica 10+ *)

Prog

(SWI-Prolog)
:- op(500, xfx, o).
b(N, B) :- (N = 0 -> B = -1 ; B is msb(N)).
t(N, T) :- N = 0, !, T = x.
t(N, T) :- b(N, A), P is N - (1 << A), b(P, B), R is A - B - 1,
    t(P, TP), t(R, TR), T = (TP o TR).
m(T, TT) :- T = x, !, TT = x.
m(T, TT) :- T = (TP o TR), m(TP, TTP), m(TR, TTR), TT = (TTR o TTP).
n(T, N) :- T = x, !, N = 0.
n(T, N) :- T = (TP o TR), n(TP, P), n(TR, R), b(P, B),
    A is R + B + 1, N is P + (1 << A).
a(N, A) :- t(N, T), m(T, TT), n(TT, A).
w(A) :- checklist(write, [A, ', ']), flush_output.
main :- forall(between(0, 33, N), (a(N, A), w(A))), nl.

Crossrefs

Cf. A324557 (fixed points of this sequence).

Sequence in context: A200714 A086702 A156140 * A069888 A073281 A130922

Adjacent sequences: A324553 A324554 A324555 * A324557 A324558 A324559

Keyword

nonn,base

Author

Luc Rousseau, Mar 06 2019

Status

approved