Math::PlanePath::FractionsTree(3pm)

1Math::PlanePath::FractiUosnesrTrCeoen(t3r)ibuted Perl DoMcautmhe:n:tPaltainoenPath::FractionsTree(3)
2
3
4

NAME

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

SYNOPSIS

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

DESCRIPTION

14       This path enumerates fractions X/Y in the range 0 < X/Y < 1 and in
15       reduced form, ie. X and Y having no common factor, using a method by
16       Johannes Kepler.
17
18       Fractions are traversed by rows of a binary tree which effectively
19       represents a coprime pair X,Y by subtraction steps of a subtraction-
20       only form of Euclid's greatest common divisor algorithm which would
21       prove X,Y coprime.  The steps left or right are encoded/decoded as an N
22       value.
23
24   Kepler Tree
25       The default and only tree currently is by Kepler.
26
27           Johannes Kepler, "Harmonices Mundi", Book III.  Excerpt of
28           translation by Aiton, Duncan and Field at
29           <http://ndirty.cute.fi/~karttu/Kepler/a086592.htm>
30
31       In principle similar bit reversal etc variations as in "RationalsTree"
32       would be possible.
33
34           N=1                             1/2
35                                     ------   ------
36           N=2 to N=3             1/3               2/3
37                                 /    \            /   \
38           N=4 to N=7         1/4      3/4      2/5      3/5
39                              | |      | |      | |      | |
40           N=8 to N=15     1/5  4/5  3/7 4/7  2/7 5/7  3/8 5/8
41
42       A node descends as
43
44                 X/Y
45               /     \
46           X/(X+Y)  Y/(X+Y)
47
48       Kepler described the tree as starting at 1, ie. 1/1, which descends to
49       two identical 1/2 and 1/2.  For the code here a single copy starting
50       from 1/2 is used.
51
52       Plotting the N values by X,Y is as follows.  Since it's only fractions
53       X/Y<1, ie. X<Y, all points are above the X=Y diagonal.  The unused X,Y
54       positions are where X and Y have a common factor.  For example X=2,Y=6
55       have common factor 2 so is never reached.
56
57           12  |    1024                  26        27                1025
58           11  |     512   48   28   22   34   35   23   29   49  513
59           10  |     256        20                  21       257
60            9  |     128   24        18   19        25  129
61            8  |      64        14        15        65
62            7  |      32   12   10   11   13   33
63            6  |      16                  17
64            5  |       8    6    7    9
65            4  |       4         5
66            3  |       2    3
67            2  |       1
68            1  |
69           Y=0 |
70                ----------------------------------------------------------
71                 X=0   1    2    3    4    5    6    7    8    9   10   11
72
73       The X=1 vertical is the fractions 1/Y at the left end of each tree row,
74       which is
75
76           Nstart=2^level
77
78       The diagonal X=Y-1, fraction K/(K+1), is the second in each row, at
79       N=Nstart+1.  That's the maximum X/Y in each level.
80
81       The N values in the upper octant, ie. above the line Y=2*X, are even
82       and those below that line are odd.  This arises since X<Y so the left
83       leg X/(X+Y) < 1/2 and the right leg Y/(X+Y) > 1/2.  The left is an even
84       N and the right an odd N.
85

FUNCTIONS

87       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
88       classes.
89
90       "$path = Math::PlanePath::FractionsTree->new ()"
91           Create and return a new path object.
92
93       "$n = $path->n_start()"
94           Return 1, the first N in the path.
95
96       "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
97           Return a range of N values which occur in a rectangle with corners
98           at $x1,$y1 and $x2,$y2.  The range is inclusive.
99
100           For reference, $n_hi can be quite large because within each row
101           there's only one new 1/Y fraction.  So if X=1 is included then
102           roughly "$n_hi = 2**max(x,y)".
103
104   Tree Methods
105       Each point has 2 children, so the path is a complete binary tree.
106
107       "@n_children = $path->tree_n_children($n)"
108           Return the two children of $n, or an empty list if "$n < 1" (before
109           the start of the path).
110
111           This is simply "2*$n, 2*$n+1".  The children are $n with an extra
112           bit appended, either a 0-bit or a 1-bit.
113
114       "$num = $path->tree_n_num_children($n)"
115           Return 2, since every node has two children, or return "undef" if
116           "$n<1" (before the start of the path).
117
118       "$n_parent = $path->tree_n_parent($n)"
119           Return the parent node of $n, or "undef" if "$n <= 1" (the top of
120           the tree).
121
122           This is simply "floor($n/2)", stripping the least significant bit
123           from $n (undoing what "tree_n_children()" appends).
124
125       "$depth = $path->tree_n_to_depth($n)"
126           Return the depth of node $n, or "undef" if there's no point $n.
127           The top of the tree at N=1 is depth=0, then its children depth=1,
128           etc.
129
130           The structure of the tree with 2 nodes per point means the depth is
131           simply floor(log2(N)), so for example N=4 through N=7 are all
132           depth=2.
133
134   Tree Descriptive Methods
135       "$num = $path->tree_num_children_minimum()"
136       "$num = $path->tree_num_children_maximum()"
137           Return 2 since every node has 2 children, making that both the
138           minimum and maximum.
139
140       "$bool = $path->tree_any_leaf()"
141           Return false, since there are no leaf nodes in the tree.
142

OEIS

144       The trees are in Sloane's Online Encyclopedia of Integer Sequences in
145       the following forms
146
147           <http://oeis.org/A020651> (etc)
148
149           tree_type=Kepler
150             A020651  - X numerator (RationalsTree AYT denominators)
151             A086592  - Y denominators
152             A086593  - X+Y sum, and every second denominator
153             A020650  - Y-X difference (RationalsTree AYT numerators)
154
155       The tree descends as X/(X+Y) and Y/(X+Y) so the denominators are two
156       copies of X+Y time after the initial 1/2.  A086593 is every second,
157       starting at 2, eliminating the duplication.  This is also the sum X+Y,
158       from value 3 onwards, as can be seen by thinking of writing a node as
159       the X+Y which would be the denominators it descends to.
160

HOME PAGE

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

LICENSE

171       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
172
173       This file is part of Math-PlanePath.
174
175       Math-PlanePath is free software; you can redistribute it and/or modify
176       it under the terms of the GNU General Public License as published by
177       the Free Software Foundation; either version 3, or (at your option) any
178       later version.
179
180       Math-PlanePath is distributed in the hope that it will be useful, but
181       WITHOUT ANY WARRANTY; without even the implied warranty of
182       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
183       General Public License for more details.
184
185       You should have received a copy of the GNU General Public License along
186       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
187
188
189
190perl v5.32.0                      2020-07-28 Math::PlanePath::FractionsTree(3)