login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

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

Table of n, a(n) for n=0..118.

A. Karttunen, How to generate A065249 and A065250

Index entries for sequences related to Stern's sequences

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 11 05:41 EST 2017. Contains 295868 sequences.