The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A065625 Table of permutations of N, each row being a generator of the "rotation group" of infinite planar binary tree. Inverse generators are given in A065626. 10
 3, 1, 1, 7, 5, 1, 2, 3, 2, 1, 6, 2, 7, 2, 1, 14, 11, 4, 3, 2, 1, 15, 6, 5, 9, 3, 2, 1, 4, 7, 3, 5, 4, 3, 2, 1, 5, 4, 15, 6, 11, 4, 3, 2, 1, 12, 10, 8, 7, 6, 5, 4, 3, 2, 1, 13, 22, 9, 4, 7, 13, 5, 4, 3, 2, 1, 28, 23, 10, 19, 8, 7, 6, 5, 4, 3, 2, 1, 29, 12, 11, 10, 9, 8, 15, 6, 5, 4, 3, 2, 1, 30, 13, 6, 11, 5, 9, 8, 7, 6, 5, 4, 3, 2, 1, 31, 14, 14, 12, 23, 10, 9, 17, 7, 6, 5, 4, 3, 2 (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: .............................1............................ .............2...............................3............ .....4...............5...............6...............7.... .8.......9.......10.....11.......12.....13.......14.....15 etc., i.e. the node Y is a descendant of the node X, iff its binary expansion (the most significant bits) begin with the binary expansion of X. In this table the n-th row is a permutation induced by the rotation of the node n right and in the table A065626 the corresponding row gives the inverse of that permutation, induced by rotation of the node n left. Particular realizations of this tree are the Christoffel tree and the Stern-Brocot tree (A007305/A007306), thus each such rotation, or composition of such rotations (e.g. A065249) induces a particular bijective function on rationals and such functions form the "group A" of the order-preserving permutations of the rational numbers as defined by Cameron. LINKS A. Karttunen, How to generate A065249 and A065250 MAPLE [seq(RotateRightTable(j), j=0..119)]; RotateRightTable := n -> RotateNodeRight(1+(n-((trinv(n)*(trinv(n)-1))/2)), (((trinv(n)-1)*(((1/2)*trinv(n))+1))-n)+1); # Rewrites t-prefixed x's in the following way: t -> t1, t1... -> t11..., t0 -> t, t01... -> t10..., t00... -> t0... and leaves other x's intact. RotateNodeRight := proc(t, x) local u, y; u := floor_log_2(t)+1; y := floor_log_2(x)+1; if(y < u) then RETURN(x); fi; if(floor(x/(2^(y-u))) <> t) then RETURN(x); fi; if(x = t) then RETURN((2*x)+1); fi; if(1 = (floor(x/(2^(y-u-1))) mod 2)) then RETURN(x + (t * 2^(y-u)) + 2^(y-u)); fi; if(y = (u+1)) then RETURN(x/2); fi; if(1 = (floor(x/(2^(y-u-2))) mod 2)) then RETURN(x + 2^(y-u-2)); fi; RETURN(x - (t * 2^(y-u-1))); end; CROSSREFS The first row (rotate the top node right): A057114, 2nd row (rotate the top node's left child): A065627, 3rd row (rotate the top node's right child): A065629, 4th row: A065631, 5th row: A065633, 6th row: A065635, 7th row: A065637, 8th row: A065639. Maple procedure floor_log_2 given in A054429, for trinv, follow A065167. Variant of the same idea: A065658. Sequence in context: A118801 A080936 A094507 * A287213 A284631 A154341 Adjacent sequences:  A065622 A065623 A065624 * A065626 A065627 A065628 KEYWORD nonn,tabl AUTHOR Antti Karttunen, Nov 08 2001 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 11 09:47 EDT 2020. Contains 336423 sequences. (Running on oeis4.)