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.
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
The first row (rotate the top node right): A065660, 2nd row (rotate the top node's left child): A065662, 3rd row (rotate the top node's right child): A065664, 4th row: A065666, 5th row: A065668, 6th row: A065670, 7th row: A065672. For the other needed Maple procedures follow A065625, A047679, A054424 and A054429. Cf. also A065674-A065676. Inverse permutations are given in A065659.
KEYWORD
nonn,tabl
AUTHOR
Antti Karttunen, Nov 22 2001
STATUS
approved