Math::PlanePath::RationalsTree -- rationals by tree
use Math::PlanePath::RationalsTree; my $path = Math::PlanePath::RationalsTree->new (tree_type => 'SB'); my ($x, $y) = $path->n_to_xy (123);
This path enumerates rational fractions X/Y in reduced form, ie. X and Y having no common factor.
Fractions are traversed by rows of a binary tree which effectively represents a coprime pair X,Y by the steps of the binary greatest common divisor algorithm which would prove X,Y coprime. The steps left or right are encoded/decoded as an N value.
There's five different types of tree. In a given tree row they all have the same set of X/Y fractions, but in a different order reflecting different encodings of the N value.
See examples/rationals-tree.pl in the PlanePath sources for a simple print of all the trees.
The default tree_type=>"SB" is the tree of Moritz Stern and Achille Brocot. The rows are fractions of increasing value.
tree_type=>"SB"
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/1
Writing the parents in between the children as an "in-order" traversal to given depth has the values in increasing order too,
1/1 1/2 | 2/1 1/3 | 2/3 | 3/2 | 3/1 | | | | | | | 1/3 1/2 2/3 1/1 3/2 2/1 3/1 ^ 4/3 goes here next
New values are a "mediant" (x1+x2)/(y1+y2) from the left and right parents in this flattening. So the 4/3 shown above is from left parent 1/1 and right parent 3/2 as 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 never reached.
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 10
The X=1 vertical is the fractions 1/Y at the left of each tree row, which is at N value
Nstart=2^level
The Y=1 horizontal is the Y/1 integers at the end each row which is
Nend=2^(level+1)-1
tree_type=>"CW" selects the tree of Neil Calkin and Herbert Wilf, "Recounting the Rationals",
tree_type=>"CW"
http://www.math.upenn.edu/%7Ewilf/website/recounting.pdf
As noted above the values within each row are the same as the Stern-Brocot, as they are for all the trees, but they're 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/1
Going 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 the 3/5 to the right. These values are Stern's diatomic sequence.
Each row is symmetric in reciprocals, ie. reading from right to left is the reciprocals of reading left to right.
A node descends as
X/Y / \ X/(X+Y) (X+Y)/Y
Taking these formulas in reverse up the tree shows how it relates to the binary greatest common divisor algorithm. At a given node the smaller of P,Q is subtracted from the bigger,
P/(Q-P) (P-Q)/P / or \ P/Q P/Q
Plotting the N values by X,Y has the same X=1 vertical and Y=1 horizontal as the SB above, but the values in between are re-ordered.
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 10
N values for the SB and CW trees are converted by reversing bits. At a given X,Y position if N = binary "1abcde" in the SB tree then at that same X,Y in the CW the N value is "1edcba". 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.
tree_type=>"AYT" selects the tree described (independently is it?) by D. N. Andreev and Shen Yu-Ting.
tree_type=>"AYT"
http://files.school-collection.edu.ru/dlrstore/d62f7b96-a780-11dc-945c-d34917fee0be/i2126134.pdf http://www.jstor.org/stable/2320374
Their constructions are a one-to-one mapping between an integer N and rational X/Y as a way of enumerating the rationals. It's not designed to be 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 again the same, but in a further 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/5
Each fraction descends as follows. The left is an increment and the right is the reciprocal of that increment.
X/Y / \ X/Y + 1 1/(X/Y + 1)
which means
X/Y / \ (X+Y)/Y Y/(X+Y)
The (X+Y)/Y leg is the same as in the CW (on the right instead of the 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, ie. at Nend=2^(level+1)-1. And as noted by Andreev successive two right legs at points N=4k+1 and N=4k+3 add up to 1, ie.
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 1
Plotting 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 10
The 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, thus N=Nstart+1 in that column.
tree_type=>"Bird" selects the Bird tree by Ralf Hinze, "Functional Pearls: The Bird tree",
tree_type=>"Bird"
http://www.cs.ox.ac.uk/ralf.hinze/publications/Bird.pdf
It'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/3
The subtrees are plus one and reciprocal, or reciprocal and plus one (ie. the other way around),
1/(tree + 1) and (1/tree) + 1
which ends up meaning Y/(X+Y) and (X+Y)/X taking N bits low to high.
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 10
Notice that unlike the other trees the X=1 vertical of fractions 1/Y are not at 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, because those integers are in the right hand half of the tree.
The Bird tree N values are related to the SB tree by inverting every second bit starting from the second after the highest 1, ie. xor "001010...". So if N=1abcdefg binary then b,d,f are inverted, ie. an xor with binary 00101010. For example 3/4 in the SB tree is at N=11 = binary 1011. Xor with 0010 for binary 1001 N=9 which is the 3/4 in the Bird tree. The same xor goes back the other way Bird tree to SB tree.
This xoring reflects the way the tree is mirrored, swapping left and right at each level. Only every second bit is inverted because mirroring twice (or any even number of times) puts it back to the ordinary way.
tree_type=>"Drib" selects the Drib tree by Ralf Hinze. It reverses the bits of N in the Bird tree (in a similar way that the SB and CW are bit reversals).
tree_type=>"Drib"
N=1 1/1 ------ ------ N=2 to N=3 1/2 2/1 / \ / \ N=4 to N=7 2/3 3/1 1/3 3/2 | | | | | | | | N=8 to N=15 3/5 5/2 1/4 4/3 3/4 4/1 2/5 5/3
The descendants of each node are
X/Y / \ Y/(X+Y) (X+Y)/X
Both ends have Fibonacci numbers, being F(k)/F(k+1) on the left and F(k+1)/F(k) on the right.
Because Drib/Bird are bit reversals like CW/SB are bit reversals, the xor procedure described above which relates Bird<->SB applies to Drib<->CW, but working from the second lowest bit upwards, ie. xor binary "0..01010". For example 4/1 is at N=15 binary 1111 in the CW tree. Xor with 0010 for 1101 N=13 which is 4/1 in the Drib tree.
In all the trees the rows are permutations of the fractions arising from the SB tree and Stern diatomic sequence. The properties of the diatomic sequence mean that within a level Nstart=2^level to Nend=2^(level+1)-1 the fractions have totals
sum fractions = (3 * 2^level - 1) / 2 sum numerators = 3^level
For example at level=2, N=4 to N=7, the fractions are 1/3, 2/3, 3/2, 3/1. The numerators 1+2+3+3 = 9 is 3^2. The sum as fractions 1/3+2/3+3/2+3/1 = 11/2 which is (3*2^2-1)/2=11/2.
The trees are in Sloane's Online Encyclopedia of Integer Sequences in the following forms
http://oeis.org/A002487 (etc) A007305 - SB numerators, Farey fractions (extra 0,1) A047679 - SB denominators A007306 - SB num+den sum, Farey 0 to 1 part (extra 1,1) A002487 - CW nums and dens, Stern diatomic sequence (extra 0) A070990 - CW den-num, Stern diatomic first differences (less 0) A020650 - AYT numerators A020651 - AYT denominators A086592 - AYT num+den sum, Kepler's left denominators A162909 - Bird numerators A162910 - Bird denominators A068611 - Drib numerators A068612 - Drib denominators
The sequences "extra ..." have one or two extra initial values over what the RationalsTree here gives, but are the same after that. The "less ..." Stern first differences has one less term.
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,$y1 and $x2,$y2. The range is inclusive.
$x1
$y1
$x2
$y2
For reference, $n_hi can be quite large because within each row there's only one new X/1 integer and 1/Y fraction. So if X=1 or Y=1 is included then roughly $n_hi = 2**max(x,y). If min(x,y) is bigger than 1 then it reduces a little to roughly 2**(max/min + min).
$n_hi
$n_hi = 2**max(x,y)
Math::PlanePath, Math::PlanePath::CoprimeColumns, Math::PlanePath::PythagoreanTree
Math::NumSeq::SternDiatomic
http://user42.tuxfamily.org/math-planepath/index.html
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/>.
To install Math::PlanePath, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::PlanePath
CPAN shell
perl -MCPAN -e shell install Math::PlanePath
For more information on module installation, please visit the detailed CPAN module installation guide.