Install Now
Math::PlanePath::FractionsTree -- fractions by tree
Contents
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.
KeplerTree
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)".
TreeMethods
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.
TreeDescriptiveMethods
"$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.
Home Page
License
Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 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/>.
perl v5.32.0 2021-01-23 Math::PlanePath::FractionsTree(3pm)
Name
Math::PlanePath::FractionsTree -- fractions by 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
Synopsis
use Math::PlanePath::FractionsTree;
my $path = Math::PlanePath::FractionsTree->new (tree_type => 'Kepler');
my ($x, $y) = $path->n_to_xy (123);
Emojis
PNG Icons