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 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 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 (bits high to low or low to high, and possible bit flip at every second position).
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/5 3/5 3/4 4/3 5/3 5/2 4/1
Writing the parents in between the children so as to make an "in-order" tree traversal to given depth puts the values in increasing order,
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
1 | 1 3 7 15 31 63 127 255 511 1023
Y=0 |
----------------------------------------------------
X=0 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
Calkin-Wilf Tree
tree_type=>"CW"
selects the tree of Neil Calkin and Herbert Wilf, "Recounting the Rationals",
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 or 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.
tree_type => "CW"
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
1 | 1 3 7 15 31 63 127 255 511 1023
Y=0 |
-------------------------------------------------------------
X=0 1 2 3 4 5 6 7 8 9 10
In each node descent the left X/(X+Y) < 1 and the right (X+Y)/Y > 1, which means even N is above the X=Y diagonal and odd N is below.
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.
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/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 the CW (which is X/(X+Y)).
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 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
tree_type => "AYT"
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
1 | 1 2 4 8 16 32 64 128 256 512
Y=0 |
----------------------------------------------------
X=0 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.
In each node descent the left (X+Y)/Y > 1 and the right Y/(X+Y) < 1, which means odd N is above the X=Y diagonal and even N is below.
The tree structure corresponds to Johannes Kepler's tree of fractions. That tree starts from 1/2 and makes fractions A/B with A<B by descending to A/(A+B) and B/(A+B). This is the same as the AYT tree with
A = Y X = B-A
B = X+Y Y = A
So the AYT denominator is the Kepler numerator, and the AYT sum num+den is the Kepler denominator. (See FractionsTree.)
Bird Tree
tree_type=>"Bird"
selects the Bird tree by Ralf Hinze, per "Functional Pearls: The Bird tree",
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,
tree_type => "Bird"
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
1 | 1 3 6 13 26 53 106 213 426 853
Y=0 |
----------------------------------------------------
X=0 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.
Drib Tree
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 of each other).
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
The endmost fractions of each row are Fibonacci numbers, F(k)/F(k+1) on the left and F(k+1)/F(k) on the right.
tree_type => "Drib"
10 | 682 50 44 852
9 | 426 58 54 40 36 340 683
8 | 170 30 16 212 427
7 | 106 18 22 24 28 84 171 59 51
6 | 42 52 107
5 | 26 14 8 20 43 19 31 55
4 | 10 12 27 23 41
3 | 6 4 11 15 25 17 45
2 | 2 7 9 29 37
1 | 1 3 5 13 21 53 85 213 341 853
Y=0 |
-------------------------------------------------------
X=0 1 2 3 4 5 6 7 8 9 10
In each node descent the left Y/(X+Y) < 1 and the right (X+Y)/X > 1, which means even N is above the X=Y diagonal and odd N is below.
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.
Common Characteristics
In all the trees the rows are permutations of the rationals arising from the SB tree and the Stern diatomic sequence. The properties of the diatomic sequence mean that within a row from Nstart=2^level to Nend=2^(level+1)-1 the rationals have totals
sum rationals = (3 * 2^level - 1) / 2
sum numerators = 3^level
For example at level=2, N=4 to N=7, the rationals are 1/3, 2/3, 3/2, 3/1. The sum of rationals 1/3+2/3+3/2+3/1 = 11/2 which is (3*2^2-1)/2=11/2. The sum of numerators 1+2+3+3 = 9 is 3^2.
All sorts of permutations are conceivable within a row, but the ones here have some relationship to X/Y descendants or tree sub-forms. There's two choices high to low or low to high N bits, and then three bit flip forms: no flips, flip every second starting from the first, or flip every second starting from the second. Only 5 of the 6 are implemented currently. The missing one is the AYT formulas done low to high. Does that have a name, or a particular significance?
OEIS
The trees are in Sloane's Online Encyclopedia of Integer Sequences in various forms,
http://oeis.org/A007305 (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 diff, Stern diatomic first diffs (less 0)
A020650 - AYT numerators
A020651 - AYT denominators (Kepler numerators)
A086592 - AYT num+den sum (Kepler denominators)
A162909 - Bird numerators
A162910 - Bird denominators
A162911 - Drib numerators
A162912 - Drib denominators
A086893 - position Fibonacci F[n+1],F[n] in Stern diatomic,
is N of F[n+1]/F[n] in CW
and N of X/1 in Drib, ie. N values in row at Y=1
A061547 - position Fibonacci F[n],F[n+1] in Stern diatomic,
is N of F[n]/F[n+1] in CW
and N of 1/Y in Drib, ie. N values in column at X=1
A054424 - permutation DiagonalRationals to SB
A054425 - DiagonalRationals to SB with 0s at non-coprimes
A054426 - inverse, SB to DiagonalRationals
A054427 - permutation coprimes to SB right hand X/Y>1
A000975 - Bird N in column X=1, being 1010 alternating bits
A088696 - length of continued fraction SB left half (num/den<1)
The sequences marked "extra ..." have one or two extra initial values over what the RationalsTree here gives, but are the same after that. And the Stern first differences "less ..." means it has one less term than what the code here gives.
FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for 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 = $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 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).
Tree Methods
@n_children = $path->tree_n_children($n)
-
Return the two children of
$n
, or an empty list if$n < 1
(ie. 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. $n_parent = $path->tree_n_parent($n)
-
Return the parent node of
$n
, orundef
if$n <= 1
(the top of the tree).This is simply
floor($n/2)
, stripping the least significant bit from$n
(undoing whattree_n_children()
appends).
SEE ALSO
Math::PlanePath, Math::PlanePath::FractionsTree, Math::PlanePath::PythagoreanTree, Math::PlanePath::CoprimeColumns, Math::PlanePath::DiagonalRationals
HOME PAGE
http://user42.tuxfamily.org/math-planepath/index.html
LICENSE
Copyright 2011, 2012 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/>.