|
|
A065658
|
|
The table of permutations of N, each row induced by the rotation (to the right) of the n-th node in the infinite binary "decimal" fraction tree.
|
|
21
|
|
|
7, 25, 1, 31, 22, 1, 1, 3, 2, 1, 223, 10, 247, 2, 1, 15, 94, 4, 3, 2815, 1, 127, 6, 5, 4, 3, 2, 1, 5, 7, 28, 5, 4, 115, 2, 1, 385, 20479, 127, 6, 94, 4, 3, 2, 1, 13, 175, 8, 7, 6, 5, 4, 3, 2, 1, 1792, 46, 9, 280, 7, 234881023, 5, 4, 3, 322, 1, 61, 382, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,1
|
|
COMMENTS
|
Consider the following infinite binary tree, where the nodes are numbered in breadth-first, left-to-right fashion from the top as in A065625 and then assigned the following rational values:
--------------------------------------(0.1)---------------------------------------
----------------(0.01)-------------------------------------(0.11)-----------------
-----(0.001)--------------(0.011)---------------(0.101)--------------(0.111)------
(0.0001)-(0.0011)----(0.0101)-(0.0111)-----(0.1001)-(0.1011)-----(0.1101)-(0.1111)
i.e., the elements (1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8, 1/16, 3/16, ..., of the Quasicyclic group Z+((2a+1)/(2^b)) for prime 2) listed here in their binary "decimal" fraction form. Subjecting this tree to any similar binary tree rotation as used in A065625 induces a permutation of the rationals in range ]0,1[ (i.e., including also the ones having infinite binary expansions, corresponding to infinite paths in above tree), which we then convert to permutations of N by taking the positions of the mapped values at the ]0,1[ side of the Stern-Brocot Tree (A007305/A007306). See example at A065670.
|
|
LINKS
|
|
|
MAPLE
|
[seq(RotateBinFracRightTable(j), j=0..119)]; RotateBinFracRightTable := n -> RotateBinFracNodeRight(1+(n-((trinv(n)*(trinv(n)-1))/2)), (((trinv(n)-1)*(((1/2)*trinv(n))+1))-n)+1);
RotateBinFracNodeRight := (t, n) -> frac2position_in_0_1_SB_tree(RotateBinFracNodeRight_x(t, SternBrocot0_1frac(n)));
RotateBinFracNodeRight_x := proc(t, x) local num, den; den := 2^(1+floor_log_2(t)); num := (2*(t-(den/2)))+1; if((x <= (num-1)/den) or (x >= (num+1)/den)) then RETURN(x); fi; if(x <= ((2*(num-1))+1)/(2*den)) then RETURN((2*(x - ((num-1)/den))) + ((num-1)/den)); fi; if(x < (num/den)) then RETURN(x + (1/(2*den))); fi; RETURN((num/den) + ((x-((num-1)/den))/2)); end;
SternBrocot0_1frac := proc(n) local m; m := n + 2^floor_log_2(n); SternBrocotTreeNum(m)/SternBrocotTreeDen(m); end;
frac2position_in_0_1_SB_tree := r -> RETURN(ReflectBinTreePermutation(cfrac2binexp(convert(1/r, confrac))));
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|