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
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
KEYWORD
nonn,base
AUTHOR
Luc Rousseau, Mar 06 2019
STATUS
approved