NAME
Math::PlanePath::RationalsTree -- rationals by tree
SYNOPSIS
use Math::PlanePath::RationalsTree;
my $path = Math::PlanePath::RationalsTree->new (tree_type => 'SB');
my ($x, $y) = $path->n_to_xy (123);DESCRIPTION
In progress.
This path enumerates reduced rational fractions X/Y with no common factor between X and Y by one of four different types of binary trees.
The trees effectively represent a coprime pair X,Y by the steps of the binary greatest common divisor algorithm which would prove X,Y coprime. The different encoding of those steps gives a different order for the X/Y values in the tree types. See examples/rationals-tree.pl in the PlanePath sources to print all four trees.
Stern-Brocot Tree
The default tree_type=>"SB" is the tree of Moritz Stern and Achille Brocot. The rows are fractions of increasing value.
N=1 1/1
------ ------
N=2 to N=3 1/2 2/1
/ \ / \
N=4 to N=7 1/3 2/3 3/2 3/1
| | | | | | | |
N=8 to N=15 1/4 2/4 3/5 3/4 4/3 5/3 5/2 4/1Writing the parents in between the children as an "in-order" traversal to given depth gives values in increasing order too,
1/1
1/2 | 2/1
1/3 | 2/3 | 3/2 | 3/1
| | | | | | |
1/2 1/2 2/3 1/1 3/2 2/1 3/1
^
4/3New values are formed by a "mediant" (x1+x2)/(y1+y2) of left and right parents based on this flattening. The 4/3 above is formed from left parent 1/1 and right parent 3/2 for mediant (1+3)/(1+2)=4/3.
Plotting the N values by X,Y is as follows. The unused X,Y positions are where X and Y have a common factor. For example X=6,Y=2 has common factor 2 so is excluded.
10 | 512 35 44 767
9 | 256 33 39 40 46 383 768
8 | 128 18 21 191 384
7 | 64 17 19 20 22 95 192 49 51
6 | 32 47 96
5 | 16 9 10 23 48 25 26 55
4 | 8 11 24 27 56
3 | 4 5 12 13 28 29 60
2 | 2 6 14 30 62
Y=1 | 1 3 7 15 31 63 127 255 511 1023
|
-------------------------------------------------------------
X=1 2 3 4 5 6 7 8 9 10The X=1 vertical is the 1/Y fractions at the start of each tree row Nstart=2^level. The Y=1 horizontal is the Y/1 integers at the end each row Nend=2^(level+1)-1.
Calkin-Wilf Tree
tree_type=>"CW" selects the tree of Neil Calkin and Herbert Wilf.
http://www.math.upenn.edu/%7Ewilf/website/recounting.pdfThe values within each row of the tree are the same as the Stern-Brocot, but in a different order.
N=1 1/1
------ ------
N=2 to N=3 1/2 2/1
/ \ / \
N=4 to N=7 1/3 3/2 2/3 3/1
| | | | | | | |
N=8 to N=15 1/4 4/3 3/5 5/2 2/5 5/3 3/4 4/1Going across by rows the denominator of one value becomes the numerator of the next. So at 4/3 the denominator 3 becomes the numerator of 3/5 to its right. Each row is symmetric too, reading from right to left is the reciprocals of left to right.
A node descends as
X/Y
/ \ applied N bits high to low
X/(X+Y) (X+Y)/YThis can can be viewed in reverse to see how it relates to the binary greatest common divisor algorithm. The smaller of P,Q is subtracted from the bigger,
P/(Q-P) (P-Q)/P
/ or \
P/Q P/QPlotting the N values by X,Y has the same X=1 vertical and Y=1 horizontal as the SB above, but the values in the middle differ.
10 | 512 56 38 1022
9 | 256 48 60 34 46 510 513
8 | 128 20 26 254 257
7 | 64 24 28 18 22 126 129 49 57
6 | 32 62 65
5 | 16 12 10 30 33 25 21 61
4 | 8 14 17 29 35
3 | 4 6 9 13 19 27 39
2 | 2 5 11 23 47
Y=1 | 1 3 7 15 31 63 127 255 511 1023
|
-------------------------------------------------------------
X=1 2 3 4 5 6 7 8 9 10N values for the SB and CW trees are converted by reversing bits. If N = binary "1abcde" in the SB tree then the same X/Y is at N = binary "1edcba" in the CW. For example at X=3,Y=4 the SB tree has N=11=0b1011 and the CW has N=14=0b1110, a reversal of the bits below the high 1.
N to X/Y in the CW tree can be calculated keeping track of just an X,Y pair and descending to X/(X+Y) or (X+Y)/Y using the bits of N from high to low. The relationship between the SB and CW N's means the same can be used to calculate the SB tree, by taking the bits of N from low to high instead.
Andreev and Yu-Ting Tree
tree_type=>"AYT" selects the tree described (independently is it?) by D. N. Andreev and Shen Yu-Ting.
http://files.school-collection.edu.ru/dlrstore/d62f7b96-a780-11dc-945c-d34917fee0be/i2126134.pdfTheir constructions are a one-to-one mapping between integer N and rational X/Y as a way of enumerating the rationals, not a tree as such, but the result is the same sort of 2^level rows as the above trees. The X/Y values within each row are the same as SB and CW, but in a different order.
N=1 1/1
------ ------
N=2 to N=3 2/1 1/2
/ \ / \
N=4 to N=7 3/1 1/3 3/2 2/3
| | | | | | | |
N=8 to N=15 4/1 1/4 4/3 3/4 5/2 2/5 5/3 3/5Each fraction descends as follows. The left is an increment and the right its reciprocal (the reciprocal of the increment).
X/Y
/ \
X/Y + 1 1/(X/Y + 1)which means
X/Y
/ \ applied N bits high to low
(X+Y)/Y Y/(X+Y)The (X+Y)/Y is the same as in the CW (on the right instead of left), but Y/(X+Y) is not the same as X/(X+Y) of the CW.
The Y/(X+Y) right leg forms the Fibonacci numbers F(k)/F(k+1) at the end of each row, at Nend=2^(level+1)-1. And as noted by Andreev successive right legs at N=4k+1 and N=4k+3 points add up to 1,
X/Y at N=4k+1 + X/Y at N=4k+3 = 1
Eg. 2/5 at N=13 and 3/5 at N=15 add up to 1Plotting the N values by X,Y gives
10 | 513 41 43 515
9 | 257 49 37 39 51 259 514
8 | 129 29 31 131 258
7 | 65 25 21 23 27 67 130 50 42
6 | 33 35 66
5 | 17 13 15 19 34 26 30 38
4 | 9 11 18 22 36
3 | 5 7 10 14 20 28 40
2 | 3 6 12 24 48
Y=1 | 1 2 4 8 16 32 64 128 256 512
|
----------------------------------------------------
X=1 2 3 4 5 6 7 8 9 10The Y=1 horizontal is the X/1 integers at Nstart=2^level. The X=1 vertical is the 1/Y fractions. Those fractions always immediately follow the corresponding integer, at N=Nstart+1.
Bird Tree
tree_type=>"Bird" selects the Bird tree by Ralf Hinze.
http://www.cs.ox.ac.uk/ralf.hinze/publications/Bird.pdfIt's expressed recursively (illustrating Haskell features) and ends up as
N=1 1/1
------ ------
N=2 to N=3 1/2 2/1
/ \ / \
N=4 to N=7 2/3 1/3 3/1 3/2
| | | | | | | |
N=8 to N=15 3/5 3/4 1/4 2/5 5/2 4/1 4/3 5/3The descendants of each node are plus one and reciprocal, or reciprocal and plus one (the other way around),
X/Y
/ \
1/(tree + 1) (1/tree) + 1which ends up meaning
X/Y
/ \ applied N bits low to high
(X+Y)/X Y/(X+Y)Plotting the N values by X,Y gives,
10 | 682 41 38 597
9 | 341 43 45 34 36 298 938
8 | 170 23 16 149 469
7 | 85 20 22 17 19 74 234 59 57
6 | 42 37 117
5 | 21 11 8 18 58 28 31 61
4 | 10 9 29 30 50
3 | 5 4 14 15 25 24 54
2 | 2 7 12 27 52
Y=1 | 1 3 6 13 26 53 106 213 426 853
----------------------------------------------------
X=1 2 3 4 5 6 7 8 9 10Notice that unlike the other trees the X=1 vertical of fractions 1/Y are not the Nstart=2^level or Nend=2^(level+1)-1 row endpoints. Those 1/Y fractions are instead on a zigzag through the middle of the tree giving binary N=1010...etc of alternate 1 and 0 bits. The integers X/1 in the Y=1 vertical are similar, but N=11010...etc starting the alternation from a 1 in the second highest bit, since those integers are in the right hand half of the tree.
FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.
$path = Math::PlanePath::RationalsTree->new ()$path = Math::PlanePath::RationalsTree->new (tree_type => $str)-
Create and return a new path object.
($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,$y1and$x2,$y2. The range is inclusive.For reference,
$n_hican be quite large because there's only one new X/1 integer and the same 1/Y fractions within each row, which means more or less$n_hi = 2**max(x,y).
SEE ALSO
Math::PlanePath, Math::PlanePath::PythagoreanTree
HOME PAGE
http://user42.tuxfamily.org/math-planepath/index.html
LICENSE
Copyright 2011 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/>.