Provided by: libmath-planepath-perl_113-1_all bug

NAME

       Math::PlanePath::FractionsTree -- fractions by tree

SYNOPSIS

        use Math::PlanePath::FractionsTree;
        my $path = Math::PlanePath::FractionsTree->new (tree_type => 'Kepler');
        my ($x, $y) = $path->n_to_xy (123);

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.

       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.

   Kepler Tree
       The default and only tree currently is by Johannes Kepler.

           "Harmonices Mundi", Book III.  Excerpt of translation by Aiton, Duncan and Field at
           <http://ndirty.cute.fi/~karttu/Kepler/a086592.htm>

       In principle similar bit reversal etc variations as in "RationalsTree" would be possible.

           N=1                             1/2
                                     ------   ------
           N=2 to N=3             1/3               2/3
                                 /    \            /   \
           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

       A node descends as

                 X/Y
               /     \
           X/(X+Y)  Y/(X+Y)

       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.

       Plotting the N values by X,Y is as follows.  Since it's only fractions X/Y<1, ie. X<Y, all
       points are above the X=Y diagonal.  The unused X,Y positions are where X and Y have a
       common factor.  For example X=2,Y=6 have common factor 2 so is never reached.

           12  |    1024                  26        27                1025
           11  |     512   48   28   22   34   35   23   29   49  513
           10  |     256        20                  21       257
            9  |     128   24        18   19        25  129
            8  |      64        14        15        65
            7  |      32   12   10   11   13   33
            6  |      16                  17
            5  |       8    6    7    9
            4  |       4         5
            3  |       2    3
            2  |       1
            1  |
           Y=0 |
                ----------------------------------------------------------
                 X=0   1    2    3    4    5    6    7    8    9   10   11

       The X=1 vertical is the fractions 1/Y at the left end of each tree row, which is

           Nstart=2^level

       The diagonal X=Y-1, fraction K/(K+1), is the second in each row, at N=Nstart+1.  That's
       the maximum X/Y in each level.

       The N values in the upper octant, ie. above the line Y=2*X, are even and those below that
       line are odd.  This arises since X<Y so the left leg X/(X+Y) < 1/2 and the right leg
       Y/(X+Y) > 1/2.  The left is an even N and the right an odd N.

FUNCTIONS

       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.

       "$path = Math::PlanePath::FractionsTree->new ()"
           Create and return a new path object.

       "$n = $path->n_start()"
           Return 1, the first N in the path.

       "($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 $x1,$y1 and
           $x2,$y2.  The range is inclusive.

           For reference, $n_hi can be quite large because within each row there's only one new
           1/Y fraction.  So if X=1 is included then roughly "$n_hi = 2**max(x,y)".

   Tree Methods
       Each point has 2 children, so the path is a complete binary tree.

       "@n_children = $path->tree_n_children($n)"
           Return the two children of $n, or an empty list if "$n < 1" (before the start of the
           path).

           This is simply "2*$n, 2*$n+1".  The children are $n with an extra bit appended, either
           a 0-bit or a 1-bit.

       "$num = $path->tree_n_num_children($n)"
           Return 2, since every node has two children, or return "undef" if "$n<1" (before the
           start of the path).

       "$n_parent = $path->tree_n_parent($n)"
           Return the parent node of $n, or "undef" if "$n <= 1" (the top of the tree).

           This is simply "floor($n/2)", stripping the least significant bit from $n (undoing
           what "tree_n_children()" appends).

       "$depth = $path->tree_n_to_depth($n)"
           Return the depth of node $n, or "undef" if there's no point $n.  The top of the tree
           at N=1 is depth=0, then its children depth=1, etc.

           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.

   Tree Descriptive Methods
       "$num = $path->tree_num_children_minimum()"
       "$num = $path->tree_num_children_maximum()"
           Return 2 since every node has 2 children, making that both the minimum and maximum.

       "$bool = $path->tree_any_leaf()"
           Return false, since there are no leaf nodes in the tree.

OEIS

       The trees are in Sloane's Online Encyclopedia of Integer Sequences in the following forms

           <http://oeis.org/A020651> (etc)

           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)

       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.

SEE ALSO

       Math::PlanePath, Math::PlanePath::RationalsTree, Math::PlanePath::CoprimeColumns,
       Math::PlanePath::PythagoreanTree

       Math::NumSeq::SternDiatomic, Math::ContinuedFraction

HOME PAGE

       <http://user42.tuxfamily.org/math-planepath/index.html>

LICENSE

       Copyright 2011, 2012, 2013 Kevin Ryde

       This file is part of Math-PlanePath.

       Math-PlanePath is free software; you can redistribute it and/or modify it under the terms
       of the GNU General Public License as published by the Free Software Foundation; either
       version 3, or (at your option) any later version.

       Math-PlanePath is distributed in the hope that it will be useful, but WITHOUT ANY
       WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
       PURPOSE.  See the GNU General Public License for more details.

       You should have received a copy of the GNU General Public License along with Math-
       PlanePath.  If not, see <http://www.gnu.org/licenses/>.