cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

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.

Original entry on oeis.org

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
Offset: 0

Views

Author

Antti Karttunen, Nov 22 2001

Keywords

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

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.
Cf. also A065934-A065935.

Programs

  • 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))));

A065934 Permutation of N induced by the order-preserving bijection QuQR1toQuQR2 on rationals.

Original entry on oeis.org

1, 5, 13, 2, 23, 25, 3, 9, 20, 11, 95, 49, 6, 223, 57, 4, 39, 80, 10, 45, 92, 47, 383, 97, 12, 415, 208, 55, 3583, 225, 29, 17, 36, 19, 159, 320, 40, 83, 42, 22, 183, 368, 46, 189, 380, 191, 1535, 193, 24, 799, 400, 103, 6655, 3328, 52, 220, 445, 895, 57343, 897
Offset: 1

Views

Author

Antti Karttunen, Dec 07 2001

Keywords

Comments

This permutation converts the domain between the mappings N2QuQR1 and N2QuQR2 given in A065936 and A065937, i.e. N2QuQR1(j) = N2QuQR2(a[j])

Links

Crossrefs

Inverse permutation: A065935. For other needed Maple procedures, see A007305, A047679 and A054424. A065939[n] = a[A065938[n]].

Programs

  • Maple
    [seq(QuQR1toQuQR2(j),j=1..128)];
QuQR1toQuQR2 := proc(n) local m; m := n + 2^floor_log_2(n); frac2position_in_whole_SB_tree(Q0_1toQ(SternBrocotTreeNum(m)/SternBrocotTreeDen(m))); end;
Q0_1toQ := proc(rr) local r,i; r := rr; i := 0; while(r >= 1/2) do r := 2*(r-(1/2)); i := i+1; od; RETURN(i + (2*r)); end;

A065937 a(n) is the integer (reduced squarefree) under the square root obtained when the inverse of Minkowski's question mark function is applied to the n-th ratio A007305(n+1)/A047679(n-1) in the full Stern-Brocot tree and zero when it results a rational value.

Original entry on oeis.org

0, 0, 0, 5, 5, 0, 0, 0, 2, 2, 0, 5, 5, 0, 0, 2, 3, 0, 3, 3, 0, 3, 2, 0, 2, 2, 0, 5, 5, 0, 0, 5, 13, 17, 2, 17, 37, 5, 13, 13, 5, 37, 17, 2, 17, 13, 5, 2, 3, 0, 3, 3, 0, 3, 2, 0, 2, 2, 0, 5, 5, 0, 0, 3, 17, 3, 37, 21, 13, 10, 37, 3, 401, 6, 13, 10, 401, 0, 17, 17, 0, 401, 10, 13, 6, 401, 3, 37
Offset: 1

Views

Author

Antti Karttunen, Dec 07 2001

Keywords

Comments

Note: the underlying function N2Q (see the Maple code) maps natural numbers 1, 2, 3, 4, 5, ..., through all the positive rationals 1/1, 1/2, 2/1, 1/3, 2/3, 3/2, 3/1, 1/4, ... bijectively to the union of positive rationals and quadratic surds.
In his "On Numbers and Games", Conway denotes Minkowski's question mark function with x enclosed in a box.

Examples

			The first few values for this mapping are
  N2Q(1)  = Inverse_of_MinkowskisQMark(1)   = 1,
  N2Q(2)  = Inverse_of_MinkowskisQMark(1/2) = 1/2,
  N2Q(3)  = Inverse_of_MinkowskisQMark(2)   = 2,
  N2Q(4)  = Inverse_of_MinkowskisQMark(1/3) = (3-sqrt(5))/2,
  N2Q(5)  = Inverse_of_MinkowskisQMark(2/3) = (sqrt(5)-1)/2,
  N2Q(6)  = Inverse_of_MinkowskisQMark(3/2) = 3/2,
  N2Q(7)  = Inverse_of_MinkowskisQMark(3)   = 3,
  N2Q(8)  = Inverse_of_MinkowskisQMark(1/4) = 1/3,
  N2Q(9)  = Inverse_of_MinkowskisQMark(2/5) = sqrt(2)-1,
  N2Q(10) = Inverse_of_MinkowskisQMark(3/5) = 2-sqrt(2).

References

  • J. H. Conway, On Numbers and Games, 2nd ed. Natick, MA: A. K. Peters, pp. 82-86 (First ed.), 2000.

Links

Crossrefs

a(n) = A065936(A065935(n)). Positions of sqrt(n) in this mapping: A065939.

Programs

  • Maple
    [seq(find_sqrt(N2Q(j)),j=1..512)];
N2Q := n -> Inverse_of_MinkowskisQMark(A007305(m+1)/A047679(m-1));
Inverse_of_MinkowskisQMark := proc(r) local x,y,b,d,k,s,i,q; x := numer(r); y := denom(r); if(1 = y) then RETURN(x/y); fi; if(2 = y) then RETURN(x/y); fi; b := []; d := []; k := 0; s := 0; i := 0; while(x <> 0) do q := floor(x/y); if(i > 0) then b := [op(b),q]; d := [op(d),x]; fi; x := 2*(x-(q*y)); if(member(x,d,'k') and (k > 1) and (b[k] <> b[k-1]) and (q <> floor(x/y))) then s := eval_periodic_confrac_tail(list2runcounts(b[k..nops(b)])); b := b[1..(k-1)]; break; fi; i := i+1; od; if(0 = k) then b := b[1..(nops(b)-1)]; b := [op(b),b[nops(b)]]; fi; RETURN(factor(eval_confrac([floor(r),op(list2runcounts([0,op(b)]))],s))); end;
eval_confrac := proc(c,z) local x,i; x := z; for i in reverse(c) do x := (`if`((0=x),x,(1/x)))+i; od; RETURN(x); end;
eval_periodic_confrac_tail := proc(c) local x,i,u,r; x := (eval_confrac(c,u) - u) = 0; r := [solve(x,u)]; RETURN(max(r[1],r[2])); end; # Note: I am not sure if the larger root is always the correct one for the inverse of Minkowski's question mark function. However, whichever root we take, it does not change this sequence, as the integer under the square root is same in both cases. - Antti Karttunen, Aug 26 2006
list2runcounts := proc(b) local a,p,y,c; if(0 = nops(b)) then RETURN([]); fi; a := []; c := 0; p := b[1]; for y in b do if(y <> p) then a := [op(a),c]; c := 0; p := y; fi; c := c+1; od; RETURN([op(a),c]); end;
find_sqrt := proc(x) local n,i,y; n := nops(x); if(n < 2) then RETURN(0); fi; if((2 = n) and (`^` = op(0,x)) and (1/2 = op(2,x))) then RETURN(op(1,x)); else for i from 0 to n do y := find_sqrt(op(i,x)); if(y <> 0) then RETURN(y); fi; od; RETURN(0); fi; end; # This returns an integer under the square-root expression in Maple.

Extensions

Description clarified by Antti Karttunen, Aug 26 2006
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.