.\" Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28) .\" .\" Standard preamble: .\" ======================================================================== .de Sp \" Vertical space (when we can't use .PP) .if t .sp .5v .if n .sp .. .de Vb \" Begin verbatim text .ft CW .nf .ne \\$1 .. .de Ve \" End verbatim text .ft R .fi .. .\" Set up some character translations and predefined strings. \*(-- will .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left .\" double quote, and \*(R" will give a right double quote. \*(C+ will .\" give a nicer C++. Capital omega is used to do unbreakable dashes and .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff, .\" nothing in troff, for use with C<>. .tr \(*W- .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' .ie n \{\ . ds -- \(*W- . ds PI pi . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch . ds L" "" . ds R" "" . ds C` "" . ds C' "" 'br\} .el\{\ . ds -- \|\(em\| . ds PI \(*p . ds L" `` . ds R" '' . ds C` . ds C' 'br\} .\" .\" Escape single quotes in literal strings from groff's Unicode transform. .ie \n(.g .ds Aq \(aq .el .ds Aq ' .\" .\" If the F register is turned on, we'll generate index entries on stderr for .\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index .\" entries marked with X<> in POD. Of course, you'll have to process the .\" output yourself in some meaningful fashion. .\" .\" Avoid warning from groff about undefined register 'F'. .de IX .. .nr rF 0 .if \n(.g .if rF .nr rF 1 .if (\n(rF:(\n(.g==0)) \{ . if \nF \{ . de IX . tm Index:\\$1\t\\n%\t"\\$2" .. . if !\nF==2 \{ . nr % 0 . nr F 2 . \} . \} .\} .rr rF .\" .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2). .\" Fear. Run. Save yourself. No user-serviceable parts. . \" fudge factors for nroff and troff .if n \{\ . ds #H 0 . ds #V .8m . ds #F .3m . ds #[ \f1 . ds #] \fP .\} .if t \{\ . ds #H ((1u-(\\\\n(.fu%2u))*.13m) . ds #V .6m . ds #F 0 . ds #[ \& . ds #] \& .\} . \" simple accents for nroff and troff .if n \{\ . ds ' \& . ds ` \& . ds ^ \& . ds , \& . ds ~ ~ . ds / .\} .if t \{\ . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u" . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u' . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u' . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u' . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u' . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u' .\} . \" troff and (daisy-wheel) nroff accents .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V' .ds 8 \h'\*(#H'\(*b\h'-\*(#H' .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#] .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H' .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u' .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#] .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#] .ds ae a\h'-(\w'a'u*4/10)'e .ds Ae A\h'-(\w'A'u*4/10)'E . \" corrections for vroff .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u' .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u' . \" for low resolution devices (crt and lpr) .if \n(.H>23 .if \n(.V>19 \ \{\ . ds : e . ds 8 ss . ds o a . ds d- d\h'-1'\(ga . ds D- D\h'-1'\(hy . ds th \o'bp' . ds Th \o'LP' . ds ae ae . ds Ae AE .\} .rm #[ #] #H #V #F C .\" ======================================================================== .\" .IX Title "Math::PlanePath::FractionsTree 3pm" .TH Math::PlanePath::FractionsTree 3pm "2014-06-14" "perl v5.20.1" "User Contributed Perl Documentation" .\" For nroff, turn off justification. Always turn off hyphenation; it makes .\" way too many mistakes in technical documents. .if n .ad l .nh .SH "NAME" Math::PlanePath::FractionsTree \-\- fractions by tree .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::FractionsTree; \& my $path = Math::PlanePath::FractionsTree\->new (tree_type => \*(AqKepler\*(Aq); \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This path enumerates fractions X/Y in the range 0 < X/Y < 1 and in reduced form, ie. X and Y having no common factor, using a method by Johannes Kepler. .PP Fractions are traversed by rows of a binary tree which effectively represents a coprime pair X,Y by subtraction steps of a subtraction-only form of Euclid's greatest common divisor algorithm which would prove X,Y coprime. The steps left or right are encoded/decoded as an N value. .SS "Kepler Tree" .IX Subsection "Kepler Tree" The default and only tree currently is by Kepler. .IX Xref "Kepler, Johannes" .Sp .RS 4 Johannes Kepler, \*(L"Harmonices Mundi\*(R", Book \s-1III. \s0 Excerpt of translation by Aiton, Duncan and Field at .RE .PP In principle similar bit reversal etc variations as in \f(CW\*(C`RationalsTree\*(C'\fR would be possible. .PP .Vb 7 \& N=1 1/2 \& \-\-\-\-\-\- \-\-\-\-\-\- \& N=2 to N=3 1/3 2/3 \& / \e / \e \& N=4 to N=7 1/4 3/4 2/5 3/5 \& | | | | | | | | \& N=8 to N=15 1/5 4/5 3/7 4/7 2/7 5/7 3/8 5/8 .Ve .PP A node descends as .PP .Vb 3 \& X/Y \& / \e \& X/(X+Y) Y/(X+Y) .Ve .PP Kepler described the tree as starting at 1, ie. 1/1, which descends to two identical 1/2 and 1/2. For the code here a single copy starting from 1/2 is used. .PP Plotting the N values by X,Y is as follows. Since it's only fractions X/Y<1, ie. X 1/2. The left is an even N and the right an odd N. .SH "FUNCTIONS" .IX Header "FUNCTIONS" See \*(L"\s-1FUNCTIONS\*(R"\s0 in Math::PlanePath for behaviour common to all path classes. .ie n .IP """$path = Math::PlanePath::FractionsTree\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::FractionsTree\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::FractionsTree->new ()" Create and return a new path object. .ie n .IP """$n = $path\->n_start()""" 4 .el .IP "\f(CW$n = $path\->n_start()\fR" 4 .IX Item "$n = $path->n_start()" Return 1, the first N in the path. .ie n .IP """($n_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)""" 4 .el .IP "\f(CW($n_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)\fR" 4 .IX Item "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)" Return a range of N values which occur in a rectangle with corners at \&\f(CW$x1\fR,\f(CW$y1\fR and \f(CW$x2\fR,\f(CW$y2\fR. The range is inclusive. .Sp For reference, \f(CW$n_hi\fR can be quite large because within each row there's only one new 1/Y fraction. So if X=1 is included then roughly \f(CW\*(C`$n_hi = 2**max(x,y)\*(C'\fR. .SS "Tree Methods" .IX Subsection "Tree Methods" Each point has 2 children, so the path is a complete binary tree. .IX Xref "Complete binary tree" .ie n .IP """@n_children = $path\->tree_n_children($n)""" 4 .el .IP "\f(CW@n_children = $path\->tree_n_children($n)\fR" 4 .IX Item "@n_children = $path->tree_n_children($n)" Return the two children of \f(CW$n\fR, or an empty list if \f(CW\*(C`$n < 1\*(C'\fR (before the start of the path). .Sp This is simply \f(CW\*(C`2*$n, 2*$n+1\*(C'\fR. The children are \f(CW$n\fR with an extra bit appended, either a 0\-bit or a 1\-bit. .ie n .IP """$num = $path\->tree_n_num_children($n)""" 4 .el .IP "\f(CW$num = $path\->tree_n_num_children($n)\fR" 4 .IX Item "$num = $path->tree_n_num_children($n)" Return 2, since every node has two children, or return \f(CW\*(C`undef\*(C'\fR if \&\f(CW\*(C`$n<1\*(C'\fR (before the start of the path). .ie n .IP """$n_parent = $path\->tree_n_parent($n)""" 4 .el .IP "\f(CW$n_parent = $path\->tree_n_parent($n)\fR" 4 .IX Item "$n_parent = $path->tree_n_parent($n)" Return the parent node of \f(CW$n\fR, or \f(CW\*(C`undef\*(C'\fR if \f(CW\*(C`$n <= 1\*(C'\fR (the top of the tree). .Sp This is simply \f(CW\*(C`floor($n/2)\*(C'\fR, stripping the least significant bit from \&\f(CW$n\fR (undoing what \f(CW\*(C`tree_n_children()\*(C'\fR appends). .ie n .IP """$depth = $path\->tree_n_to_depth($n)""" 4 .el .IP "\f(CW$depth = $path\->tree_n_to_depth($n)\fR" 4 .IX Item "$depth = $path->tree_n_to_depth($n)" Return the depth of node \f(CW$n\fR, or \f(CW\*(C`undef\*(C'\fR if there's no point \f(CW$n\fR. The top of the tree at N=1 is depth=0, then its children depth=1, etc. .Sp The structure of the tree with 2 nodes per point means the depth is simply floor(log2(N)), so for example N=4 through N=7 are all depth=2. .SS "Tree Descriptive Methods" .IX Subsection "Tree Descriptive Methods" .ie n .IP """$num = $path\->tree_num_children_minimum()""" 4 .el .IP "\f(CW$num = $path\->tree_num_children_minimum()\fR" 4 .IX Item "$num = $path->tree_num_children_minimum()" .PD 0 .ie n .IP """$num = $path\->tree_num_children_maximum()""" 4 .el .IP "\f(CW$num = $path\->tree_num_children_maximum()\fR" 4 .IX Item "$num = $path->tree_num_children_maximum()" .PD Return 2 since every node has 2 children, making that both the minimum and maximum. .ie n .IP """$bool = $path\->tree_any_leaf()""" 4 .el .IP "\f(CW$bool = $path\->tree_any_leaf()\fR" 4 .IX Item "$bool = $path->tree_any_leaf()" Return false, since there are no leaf nodes in the tree. .SH "OEIS" .IX Header "OEIS" The trees are in Sloane's Online Encyclopedia of Integer Sequences in the following forms .Sp .RS 4 (etc) .RE .PP .Vb 5 \& tree_type=Kepler \& A020651 \- X numerator (RationalsTree AYT denominators) \& A086592 \- Y denominators \& A086593 \- X+Y sum, and every second denominator \& A020650 \- Y\-X difference (RationalsTree AYT numerators) .Ve .PP The tree descends as X/(X+Y) and Y/(X+Y) so the denominators are two copies of X+Y time after the initial 1/2. A086593 is every second, starting at 2, eliminating the duplication. This is also the sum X+Y, from value 3 onwards, as can be seen by thinking of writing a node as the X+Y which would be the denominators it descends to. .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::RationalsTree, Math::PlanePath::CoprimeColumns, Math::PlanePath::PythagoreanTree .PP Math::NumSeq::SternDiatomic, Math::ContinuedFraction .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2011, 2012, 2013, 2014 Kevin Ryde .PP This file is part of Math-PlanePath. .PP Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the \s-1GNU\s0 General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. .PP Math-PlanePath is distributed in the hope that it will be useful, but \&\s-1WITHOUT ANY WARRANTY\s0; without even the implied warranty of \s-1MERCHANTABILITY\s0 or \s-1FITNESS FOR A PARTICULAR PURPOSE. \s0 See the \s-1GNU\s0 General Public License for more details. .PP You should have received a copy of the \s-1GNU\s0 General Public License along with Math-PlanePath. If not, see .