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
This path enumerates reduced rational fractions X/Y with no common factor between X and Y by one of five 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 in N gives a different order for the X/Y values in the tree types.
See examples/rationals-tree.pl in the PlanePath sources for a simple print of all the 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/3 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. These values are Stern's diatomic sequence.
Each row is symmetric, 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.pdf
http://www.jstor.org/stable/2320374Their 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
/ \ (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),
1/(tree + 1) and (1/tree) + 1which 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 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.
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. "001010...". So if N=1abcdefg binary then b,d,f are inverted, ie. an xored 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 the Bird tree to the 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.
Drib Tree
tree_type=>"Drib" selects the Drib tree by Ralf Hinze. It reverses the bits of N in the Bird tree.
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/3The descendants of each node are
X/Y
/ \
Y/(X+Y) (X+Y)/XBoth ends are Fibonacci numbers F(k)/F(k+1) on the left and F(k+1)/F(k) on the right.
The bit reversal between the Bird and Drib trees is the same as between the SB and CW trees. This means the N xor described above which relates Bird and SB applies similarly to Drib and CW, but starting from the second lowest instead of the second highest bits, ie. 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.
Common Characteristics
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^levelFor 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=11, over 2.
OEIS
Some of the trees are in Sloane's Online Encyclopedia of Integer Sequences.
http://oeis.org/A002487
A002487 - Stern's diatomic sequence, num/den of CW tree
A162909 - Bird tree numerators
A162910 - Bird tree denominators
A068611 - Drib tree numerators
A068612 - Drib tree denominatorsFUNCTIONS
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::CoprimeColumns, 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/>.