A065658 -id:A065658 - cp's OEIS frontend

A065668 Permutation of N induced by rotating the node 5 right in the infinite planar binary tree shown at A065658.

1, 2815, 3, 4, 94, 6, 7, 8, 1279, 46, 382, 12, 13, 14, 15, 16, 17, 154, 160, 11773, 751, 190, 1534, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 2431, 157, 10485760, 328, 724, 47110, 748, 23, 3040, 3055, 766, 6142, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58

Offset: 1

Antti Karttunen, Nov 22 2001

nonn

Index entries for sequences that are permutations of the natural numbers

The fifth row of A065658. Inverse of A065669.

[seq(RotateBinFracNodeRight(5,j),j=1..256)];

A065669 Permutation of N induced by rotating the node 5 left in the infinite planar binary tree shown at A065658.

Original entry on oeis.org

1, 76, 3, 4, 167772160, 6, 7, 8, 292, 79, 658, 12, 13, 14, 15, 16, 17, 1156, 148, 2527, 40948, 322, 43, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 4612, 580, 75775, 601, 313, 2530, 163585, 655357, 20536, 10384, 10, 88, 48, 49, 50, 51, 52, 53, 54, 55, 56

Offset: 1

Antti Karttunen, Nov 22 2001

nonn

Index entries for sequences that are permutations of the natural numbers

The fifth row of A065659. Inverse of A065668.

[seq(RotateBinFracNodeLeft(5,j),j=1..256)];

A065670 Permutation of N induced by rotating the node 6 right in the infinite planar binary tree shown at A065658.

Original entry on oeis.org

1, 2, 115, 4, 5, 234881023, 7, 8, 9, 10, 11, 877, 112, 475, 15, 16, 17, 18, 19, 20, 21, 22, 23, 52, 445, 57355, 3616, 235, 1915, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 103, 13, 14191, 28615, 917506, 229630, 3613, 454, 934, 120832

Offset: 1

Antti Karttunen, Nov 22 2001

nonn

			This permutation touches only the rationals in the range ]1/2, 3/4[, which for example contains the sixth node = 3/5 of the SB ]0,1[ tree (A007305/A007306) which has an infinite, but periodic binary fractional expansion 0.100110011001... and by this permutation it is changed to 0.1010100110011001... = 53/80, which is located as the 234881023th node in the SB ]0,1[ tree.

Index entries for sequences that are permutations of the natural numbers

The sixth row of A065658. Inverse of A065671.

[seq(RotateBinFracNodeRight(6,j),j=1..256)];

A065671 Permutation of N induced by rotating the node 6 left in the infinite planar binary tree shown at A065658.

Original entry on oeis.org

1, 2, 3328, 4, 5, 97, 7, 8, 9, 10, 11, 385, 49, 1792, 15, 16, 17, 18, 19, 20, 21, 22, 23, 1537, 193, 784, 12802, 223, 229, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 6145, 769, 3088, 3103, 24, 787, 51193, 811, 439, 14680063, 226, 3712

Offset: 1

Antti Karttunen, Nov 22 2001

nonn

Index entries for sequences that are permutations of the natural numbers

The sixth row of A065659. Inverse of A065670.

[seq(RotateBinFracNodeLeft(6,j),j=1..256)];

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.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Nov 08 2001

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.

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.

[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;

A065659 The table of permutations of N, each row induced by the rotation (to the left) of the n-th node in the infinite binary "decimal" fraction tree.

Original entry on oeis.org

4, 16, 1, 22, 136, 1, 64, 3, 2, 1, 8, 64, 25, 2, 1, 160, 19, 4, 3, 76, 1, 1, 6, 5, 4, 3, 2, 1, 256, 7, 97, 5, 4, 3328, 2, 1, 32, 256, 13, 6, 167772160, 4, 3, 2, 1, 67, 1054, 8, 7, 6, 5, 4, 3, 2, 1, 34, 4, 9, 130, 7, 97, 5, 4, 3, 1249, 1, 1279, 40, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 12

Offset: 0

Antti Karttunen, Nov 22 2001

See the comment at A065658.

Index entries for sequences related to Stern's sequences

The first row (rotate the top node left): A065661, 2nd row (rotate the top node's left child): A065663, 3rd row (rotate the top node's right child): A065665, 4th row: A065667, 5th row: A065669, 6th row: A065671, 7th row: A065673. Cf. also A065674-A065676. For the other needed Maple procedures follow A065658 which gives the inverse permutations.

[seq(RotateBinFracLeftTable(j),j=0..119)]; RotateBinFracLeftTable := n -> RotateBinFracNodeLeft(1+(n-((trinv(n)*(trinv(n)-1))/2)),(((trinv(n)-1)*(((1/2)*trinv(n))+1))-n)+1);
RotateBinFracNodeLeft := (t,n) -> frac2position_in_0_1_SB_tree(RotateBinFracNodeLeft_x(t,SternBrocot0_1frac(n)));
RotateBinFracNodeLeft_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)/(2*den)) then RETURN(((num-1)/den) + (2*(x - (num/den)))); fi; if(x > (num/den)) then RETURN(x - (1/(2*den))); fi; RETURN(((num-1)/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))));

A065674 Positions of the elements of the quasicyclic group Z+(2a+1)/(2^b) [a > 0 and a < 2^(b-1), b > 0] at the ]0,1[ side of the Stern-Brocot Tree (A007305/A007306).

Original entry on oeis.org

1, 4, 7, 64, 10, 13, 127, 16384, 67, 79, 46, 49, 112, 124, 32767, 1073741824, 2050, 262, 139, 151, 2560, 352, 766, 769, 415, 3583, 232, 244, 505, 4093, 2147483647, 4611686018427387904, 4194307, 32776, 16447, 16639, 1057, 34816, 571, 583, 310

Offset: 1

Antti Karttunen, Nov 22 2001

nonn

			The fraction 1/2 is at the root (position 1), 1/4 is the left child of its left child, in the position 4 (when the tree is traversed in left-to-right, breadth-first fashion), while 3/4 is the right child of the right child of the root (pos. 7), 1/8 is at the position 64 (6 steps down the left branch from the root) and 3/8 is the right child of the left child of the root, at the position 10, etc.

Sean A. Irvine, Java program (github)
Index entries for sequences related to Stern's sequences

Permutation of A065810. Cf. A065658, A065675.

QuasiCyclics2_pos_in_0_1_SB_tree := proc(t) local num,den; den := 2^(1+floor_log_2(t)); num := (2*(t-(den/2)))+1; RETURN(frac2position_in_0_1_SB_tree(num/den)); end;
[seq(QuasiCyclics2_pos_in_0_1_SB_tree(j), j=1..128)]
# For missing Maple functions follow A065658.

A065938 Position of sqrt(n) in the mapping N2QuQR1 given in A065936.

Original entry on oeis.org

1, 6, 14, 7, 120, 248, 16160, 1019, 127, 32640, 65408, 16373, 8386032, 4194056, 4194239, 32767, 2147450880, 4294934528, 4611672824287851743, 268435343, 8796091842564, 1125899889968159, 70368744112268, 70368744161279

Offset: 1

Antti Karttunen, Dec 07 2001

nonn

Eric Weisstein's World of Mathematics, Continued Fraction.

Cf. A003285. N2QuQR1(a[n])^2 = n, see A065936. For frac2position_in_0_1_SB_tree see A065658. Cf. also A065939.

[seq(frac2position_in_0_1_SB_tree(sqrt_n_confrac2binfrac(j)),j=1..40)];
sqrt_n_confrac2binfrac := proc(n) local c,t; c := CONFRACS_FOR_sqrt_N[n]; t := `if`((1 = nops(c)),[],`if`((0 = (nops(c) mod 2)),[op(c[2..nops(c)]),op(c[2..nops(c)])],c[2..nops(c)])); RETURN( (((2^c[1])-1) + `if`(1 = nops(c),0,(runcounts2binexp0(t) / ((2^(convert(t,`+`)))-1)))) / (2^c[1])); end;
runcounts2binexp0 := proc(c) local i,e,n; n := 0; for i from 0 to nops(c)-1 do e := c[i+1]; n := ((2^e)*n) + ((i mod 2)*((2^e)-1)); od; RETURN(n); end;
CONFRACS_FOR_sqrt_N := [[1], [1, 2], [1, 1, 2], [2], [2, 4], [2, 2, 4], [2, 1, 1, 1, 4], [2, 1, 4], [3], [3, 6], etc., adapted from Weisstein's encyclopedia entry for Continued Fractions]

A065675 The exponent of 2 in the fractions of the range ]0,1[ Stern-Brocot tree (A007305/A007306) [1/2, 1/3, 2/3, 1/4, 2/5, 3/5, 3/4, 1/5, 2/7, 3/8, 3/7, 4/7, 5/8, 5/7, 4/5, ...].

Original entry on oeis.org

-1, 0, 1, -2, 1, 0, -2, 0, 1, -3, 0, 2, -3, 0, 2, -1, 1, 0, -1, 2, 0, -2, 2, 0, -2, 3, 0, -1, 3, 0, -1, 0, 1, -1, 0, 2, -1, 0, 2, -1, 0, 3, -1, 0, 3, -4, 0, 1, -4, 0, 1, -1, 0, 2, -1, 0, 2, -1, 0, 1, -1, 0, 1, -3, 1, 0, -4, 2, 0, -1, 2, 0, -1, 3, 0, -3, 3, 0, -4, 1, 0, -1, 1, 0, -1, 2, 0, -1, 2, 0, -1, 1, 0, -2, 1, 0, -2, 1, 0, -1, 1, 0, -1, 1, 0, -1, 1, 0

Offset: 1

Antti Karttunen, Nov 22 2001

sign

The exponent is negative when the denominator (A007306) is even. These occur as every third term.

Index entries for sequences related to Stern's sequences

Cf. A065674, A065676, A065658.

[seq(exp_of_2(SternBrocot0_1frac(j)),j=1..128)];
SternBrocot0_1frac := proc(n) local m; m := n + 2^floor_log_2(n); SternBrocotTreeNum(m)/SternBrocotTreeDen(m); end;
exp_of_2 := proc(x) local f,m; f := ifactors(x)[2]; for m in f do if(2 = m[1]) then RETURN(m[2]); fi; od; RETURN(0); end;

A065676 The exponent of 2 in the fractions of the whole ]0, inf[ Stern-Brocot tree (A007305/A047679) [1/1, 1/2, 2/1, 1/3, 2/3, 3/2, 3/1, 1/4, 2/5, 3/5, 3/4, 4/3, 5/3, 5/2, 4/1, ...].

Original entry on oeis.org

0, -1, 1, 0, 1, -1, 0, -2, 1, 0, -2, 2, 0, -1, 2, 0, 1, -3, 0, 2, -3, 0, 2, -2, 0, 3, -2, 0, 3, -1, 0, -1, 1, 0, -1, 2, 0, -2, 2, 0, -2, 3, 0, -1, 3, 0, -1, 1, 0, -3, 1, 0, -3, 2, 0, -2, 2, 0, -2, 1, 0, -1, 1, 0, 1, -1, 0, 2, -1, 0, 2, -1, 0, 3, -1, 0, 3, -4, 0, 1, -4, 0, 1, -1, 0, 2, -1, 0, 2, -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1, -2, 0, 1, -2, 0, 1, -1

Offset: 1

Antti Karttunen, Nov 22 2001

sign

Index entries for sequences related to Stern's sequences

Cf. A065675, A065674, A065658.

[seq(exp_of_2(SternBrocotTreeNum(j)/SternBrocotTreeDen(j)),j=1..128)];

cp's OEIS Frontend

A065668 Permutation of N induced by rotating the node 5 right in the infinite planar binary tree shown at A065658.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A065669 Permutation of N induced by rotating the node 5 left in the infinite planar binary tree shown at A065658.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A065670 Permutation of N induced by rotating the node 6 right in the infinite planar binary tree shown at A065658.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A065671 Permutation of N induced by rotating the node 6 left in the infinite planar binary tree shown at A065658.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A065659 The table of permutations of N, each row induced by the rotation (to the left) of the n-th node in the infinite binary "decimal" fraction tree.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A065674 Positions of the elements of the quasicyclic group Z+(2a+1)/(2^b) [a > 0 and a < 2^(b-1), b > 0] at the ]0,1[ side of the Stern-Brocot Tree (A007305/A007306).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A065938 Position of sqrt(n) in the mapping N2QuQR1 given in A065936.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A065675 The exponent of 2 in the fractions of the range ]0,1[ Stern-Brocot tree (A007305/A007306) [1/2, 1/3, 2/3, 1/4, 2/5, 3/5, 3/4, 1/5, 2/7, 3/8, 3/7, 4/7, 5/8, 5/7, 4/5, ...].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A065676 The exponent of 2 in the fractions of the whole ]0, inf[ Stern-Brocot tree (A007305/A047679) [1/1, 1/2, 2/1, 1/3, 2/3, 3/2, 3/1, 1/4, 2/5, 3/5, 3/4, 4/3, 5/3, 5/2, 4/1, ...].

Views