Provided by: libmath-planepath-perl_122-1_all 
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 Kepler.
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, 2014, 2015 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/>.