|
%I #16 May 23 2019 14:34:55
%S 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,
%T 2048,131072,512,340282366920938463463374607431768211456,4294967296,
%U 115792089237316195423570985008687907853269984665640564039457584007913129639936,65536,13,23
%N a(n) is the image of n obtained by a transformation on binary trees (see comments).
%C 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))).
%C 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).
%H Luc Rousseau, <a href="/A324556/a324556.svg">Helper hierarchic tree of the numbers from 0 to 31 </a>
%F a(a(n)) = n.
%F a(n) = n iff n is in A324557.
%e 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:
%e 11
%e / \
%e 3 1
%e Pursuing the decomposition process yields the complete decomposition tree:
%e 11
%e / \
%e / \
%e / \
%e 3 1
%e / \ / \
%e 1 0 0 0
%e / \
%e 0 0
%e Erase the numerical values other than 0:
%e .
%e / \
%e / \
%e / \
%e . .
%e / \ / \
%e . 0 0 0
%e / \
%e 0 0
%e Apply reflection operator:
%e .
%e / \
%e / \
%e / \
%e . .
%e / \ / \
%e 0 0 0 .
%e / \
%e 0 0
%e Compute new numerical values from the leaves up:
%e 9
%e / \
%e / \
%e / \
%e 1 2
%e / \ / \
%e 0 0 0 1
%e / \
%e 0 0
%e The root node has value 9, so a(11) = 9.
%t f[0] = {};
%t f[n_] := f /@ {FromDigits[#, 2], First@FirstPosition[#, 1, {Length@# + 1}] - 1} &@ Rest@IntegerDigits[n, 2];
%t g[{}] = 0;
%t g[{l_, r_}] := FromDigits[Join[{1}, ConstantArray[0, g[r]], If[# == 0, {}, IntegerDigits[#, 2]] &[g[l]]], 2];
%t rev[{}] = {};
%t rev[{l_, r_}] := {rev@r, rev@l};
%t Table[g[rev[f[n]]], {n, 40}]
%t (* _Andrey Zabolotskiy_, May 20 2019; requires Mathematica 10+ *)
%o (SWI-Prolog)
%o :- op(500, xfx, o).
%o b(N, B) :- (N = 0 -> B = -1 ; B is msb(N)).
%o t(N, T) :- N = 0, !, T = x.
%o t(N, T) :- b(N, A), P is N - (1 << A), b(P, B), R is A - B - 1,
%o t(P, TP), t(R, TR), T = (TP o TR).
%o m(T, TT) :- T = x, !, TT = x.
%o m(T, TT) :- T = (TP o TR), m(TP, TTP), m(TR, TTR), TT = (TTR o TTP).
%o n(T, N) :- T = x, !, N = 0.
%o n(T, N) :- T = (TP o TR), n(TP, P), n(TR, R), b(P, B),
%o A is R + B + 1, N is P + (1 << A).
%o a(N, A) :- t(N, T), m(T, TT), n(TT, A).
%o w(A) :- checklist(write, [A, ', ']), flush_output.
%o main :- forall(between(0, 33, N), (a(N, A), w(A))), nl.
%Y Cf. A324557 (fixed points of this sequence).
%K nonn,base
%O 0,3
%A _Luc Rousseau_, Mar 06 2019
|
