NAME
Math::PlanePath::MathImagePythagoreanTree -- primitive pythagorean triples by tree
SYNOPSIS
use Math::PlanePath::MathImagePythagoreanTree;
my $path = Math::PlanePath::MathImagePythagoreanTree->new
(tree_type => 'UAD',
coordinates => 'AB');
my ($x, $y) = $path->n_to_xy (123);DESCRIPTION
In progress.
This path enumerates primitive Pythagorean triples by a breadth-first traversal of a ternary tree, either a "UAD" or "FB" tree.
Each point is an integer X,Y = A,B with an integer hypotenuse A^2+B^2=C^2. A primitive triple is one where A and B have no common factor. A primitive triple always has one leg odd and the other even and the trees here give them ordered as A odd and B even.
In this breadth-first order both trees go out to rather large A,B values while smaller ones have yet to come out. The UAD tree goes out further than the FB.
UAD Tree
The UAD tree by Berggren (1934), later independently by Barning (1963), Hall (1970), and a number of others, uses three matrices U, A and D which can be multiplied onto an existing primitive triple to form three new triples.
my $path = Math::PlanePath::MathImagePythagoreanTree->new
(tree_type => 'UAD');Starting from A=3,B=4,C=5 (the well-known 3^2 + 4^2 = 5^2) this visits all and only primitive triples.
Y=40 | 14
|
|
|
| 7
Y=24 | 5
|
Y=20 | 3
|
Y=12 | 2 13
|
| 4
Y=4 | 1
|
+--------------------------------------------------
X=3 X=15 X=20 X=35 X=45The starting point N=1 is X=3,Y=4, from which three further N=2,3,4 are derived, then three more from each of those, etc,
N=1 N=2..4 N=5..13 N=14...
+-> 7,24
+-> 5,12 --+-> 55,48
| +-> 45,28
|
| +-> 39,80
3,4 --+-> 21,20 --+-> 119,120
| +-> 77,36
|
| +-> 33,56
+-> 15,8 --+-> 65,72
+-> 35,12Counting N=1 as level k=1, each level has 3^(k-1) many points so the first N for a level is
N = 1 + 3 + 3^2 + ... + 3^(k-1)
= (3^k + 1) / 2Taking the middle "A" direction at each node, so 21,20 then 119,120 then 697,696, etc, gives the triples with legs differing by 1 and thus just below the X=Y leading diagonal. These are at N=3^k.
Taking the lower "D" direction at each node, ie. 15,8 then 35,12 then 63,16, etc, is the primitives among a sequence of triples known to the ancients,
A = k^2-1, B = 2*k, C = k^2+1With k even these are primitive. (If k is odd then A and B are both even, ie. a common factor of 2, so not primitive.) These points are the end of each level, so N=(3^k-1)/2.
FB Tree
The FB tree by H. Lee Price is based on expressing triples in certain "Fibonacci boxes" with q',q,p,p' having p=q+q' and p'=p+q, so each is the sum of the preceding two similar to the Fibonacci sequence. Any box where p and q have no common factor corresponds to a primitive triple per "UV Coordinates" below.
my $path = Math::PlanePath::MathImagePythagoreanTree->new
(tree_type => 'FB');To a given box three transformations can be applied to go to new boxes corresponding to new triples. This visits all and only primitive triples, but in a different order and different tree structure to the UAD above.
Y=40 | 5
|
|
|
| 17
Y=24 | 4
|
| 8
|
Y=12 | 2 6
|
| 3
Y=4 | 1
|
+----------------------------------------------
X=3 X=15 x=21 X=35The first point N=1 is again at X=3,Y=4 and three further points N=2,3,4 are derived, then three more from each of those, etc.
N=1 N=2..4 N=5..13 N=14...
+-> 9,40
+-> 5,12 --+-> 35,12
| +-> 11,60
|
| +-> 21,20
3,4 --+-> 15,8 --+-> 55,48
| +-> 39,80
|
| +-> 13,84
+-> 7,24 --+-> 63,16
+-> 15,112UV Coordinates
Primitive Pythagorean triples can be parameterized as follows, taking A odd and B even.
A = u^2 - v^2, B = 2*u*v, C = u^2 + v^2
u = sqrt((C+A)/2), v = sqrt((C-A)/2)
with u>v>=1, one odd, one even, and no common factorThe first u=2,v=1 is the triple A=3,B=4,C=5. The coordinates option on the path gives these u,v values as the returned X,Y coordinates,
my $path = Math::PlanePath::MathImagePythagoreanTree-E<gt>new
(tree_type => 'UAD', # or 'FB'
coordinates => 'PQ');
my ($u,$v) = $path->n_to_xy(1); # u=2,v=1Since u>v>=1, the values fall in an octant below the X=Y leading diagonal,
11 | *
10 | *
9 | *
8 | * *
7 | * * *
6 | * *
5 | * * *
4 | * * * *
3 | * * *
2 | * * * * *
1 | * * * * * *
+------------------------
2 3 4 5 6 7 8 9 ...The correspondence between u,v and A,B means the trees visit all u,v with no common factor and one of them even. Of course there's other ways to iterate through such u,v, such as simply u=2,3,etc, which would generate triples too, in a different order from the trees here.
FUNCTIONS
$path = Math::PlanePath::MathImagePythagoreanTree->new ()-
Create and return a new path object.
($x,$y) = $path->n_to_xy ($n)-
Return the X,Y coordinates of point number
$non the path. Points begin at 0 and if$n < 0then the return is an empty list.Fractional positions give an X,Y position along a straight line between the integer positions. Integer positions are always just 1 apart either horizontally or vertically, so the effect is that the fraction part appears either added to or subtracted from X or Y.
SEE ALSO
H. Lee Price, "The Pythagorean Tree: A New Species", 2008, <http://arxiv.org/abs/0809.4324>.
HOME PAGE
http://user42.tuxfamily.org/math-image/index.html
LICENSE
Math-Image is Copyright 2010, 2011 Kevin Ryde
Math-Image 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-Image 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-Image. If not, see <http://www.gnu.org/licenses/>.