Provided by: libmath-planepath-perl_113-1_all 
NAME
Math::PlanePath::PythagoreanTree -- primitive Pythagorean triples by tree
SYNOPSIS
use Math::PlanePath::PythagoreanTree;
my $path = Math::PlanePath::PythagoreanTree->new
(tree_type => 'UAD',
coordinates => 'AB');
my ($x, $y) = $path->n_to_xy (123);
DESCRIPTION
This path enumerates primitive Pythagorean triples by a breadth-first traversal of one of
three ternary trees,
"UAD" Berggren, and others
"FB" Price
"UMT" a third form
Each X,Y point is a pair of integer A,B sides of a right triangle. The points are
"primitive" in the sense that the sense that A and B have no common factor.
A^2 + B^2 = C^2 gcd(A,B)=1, no common factor
X=A, Y=B
^ * ^
/ /| | right triangle
C / | B A side odd
/ / | | B side even
v *---* v C hypotenuse all integers
<-A->
A primitive triple always has one of A,B odd and the other even. The trees here have
triples ordered as A odd and B even.
The trees are traversed breadth-first and tend to go out to rather large A,B values while
yet to complete smaller ones. The UAD tree goes out further than the FB. See the
author's mathematical write-up for a proof of the UMT and that these are the only trees
with a fixed set of matrices.
<http://user42.tuxfamily.org/triples/index.html>
UAD Tree
The UAD tree by Berggren (1934) and later independently by Barning (1963), Hall (1970),
and other authors, uses three matrices U, A and D which can be multiplied onto an existing
primitive triple to form three further new primitive triples.
tree_type => "UAD" (the default)
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=45
The UAD matrices are
1 -2 2 1 2 2 -1 2 2
U = 2 -1 2 A = 2 1 2 D = -2 1 2
2 -2 3 2 2 3 -2 2 3
They're multiplied on the right of an (A,B,C) column vector, for example
/ 3 \ / 5 \
U * | 4 | = | 12 |
\ 5 / \ 13 /
The starting point is N=1 at X=3,Y=4 which is the well-known triple
3^2 + 4^2 = 5^2
From it three further points N=2, N=3 and N=4 are derived, then three more from each of
those, etc,
depth=0 depth=1 depth=2 depth=3
N=1 N=2..4 N=5..13 N=14...
+-> 7,24 A,B coordinates
+-> 5,12 --+-> 55,48
| +-> 45,28
|
| +-> 39,80
3,4 --+-> 21,20 --+-> 119,120
| +-> 77,36
|
| +-> 33,56
+-> 15,8 --+-> 65,72
+-> 35,12
Counting N=1 as depth=0, each level has 3^depth many points and the first N of a level
("tree_depth_to_n()") is at
Nrow = 1 + (1 + 3 + 3^2 + ... + 3^(depth-1))
= (3^depth + 1) / 2
The level numbering is like a mixed-radix representation of N where the high digit is
binary (so always 1) and the digits below are ternary.
+--------+---------+---------+-- --+---------+
N = | binary | ternary | ternary | ... | ternary |
+--------+---------+---------+-- --+---------+
1 0,1,2 0,1,2 0,1,2
The number of ternary digits is the "depth" and their value without the high binary 1 is
the position in the row.
A Repeatedly
Taking the middle "A" matrix repeatedly gives
3,4 -> 21,20 -> 119,120 -> 697,696 -> etc
which are the triples with legs A,B differing by 1 and therefore just above or below the
X=Y leading diagonal. The N values are 1,3,9,27,etc = 3^depth.
D Repeatedly
Taking the lower "D" matrix repeatedly gives
3,4 -> 15,8 -> 35,12 -> 63,16 -> etc
which is the primitives among a sequence of triples known to the ancients (Dickson's
History of the Theory of Numbers, start of chapter IV),
A = k^2-1 k even for primitives
B = 2*k
C = k^2+1 so C=A+2
When k is 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 last of each level, so at
N=(3^(depth+1)-1)/2 which is "tree_depth_to_n_end()".
U Repeatedly
Taking the upper "U" matrix repeatedly gives
3.4 -> 5,12 -> 7,24 -> 9,40 -> etc
with C=B+1 and A the odd numbers. These are the first of each level so at Nrow described
above. The resulting triples are a sequence known to Pythagoras (Dickson's History of the
Theory of Numbers, start of chapter IV).
A = any odd integer, so A^2 any odd square
B = (A^2-1)/2
C = (A^2+1)/2
/ A^2-1 \ / A^2+1 \
A^2 + | ------ |^2 = | ----- |^2
\ 2 / \ 2 /
This is also described by Fibonacci in his Liber Quadratorum (Book of Squares) in terms of
sums of odd numbers
s = any odd square = A^2
B^2 = 1 + 3 + 5 + ... + s-2 = ((s-1)/2)^2
C^2 = 1 + 3 + 5 + ... + s-2 + s = ((s+1)/2)^2
so C^2 = A^2 + B^2
eg. s=25=A^2 B^2=((25-1)/2)^2=144 so A=5,B=12
The geometric interpretation is that an existing square of side B is extended by a
"gnomon" around two sides making a new larger square of side C=B+1. The length of the
gnomon is odd and when it's an odd square then the new total area is the sum of two
squares.
*****gnomon******* gnomon length an odd square = A^2
+--------------+ *
| | * so new bigger square area
| square | * C^2 = A^2 + B^2
| with side B | *
| | *
+--------------+ *
See Math::PlanePath::Corner for a path following such gnomons.
UArD Tree
Option "tree_type => "UArD"" varies the UAD tree by taking points within a row in ternary
reflected Gray code order. The 3 children under each node are unchanged, just their
order.
+-> 7,24 tree_type => "UArD"
+-> 5,12 --+-> 55,48 A,B coordinates
| +-> 45,28
|
| +-> 77,36 <-+- U,D legs swapped
3,4 --+-> 21,20 --+-> 119,120 |
| +-> 39,80 <-+
|
| +-> 33,56
+-> 15,8 --+-> 65,72
+-> 35,12
Notice the middle points 77,36 and 39,80 are swapped relative to the UAD shown above. In
general the whole tree underneath an "A" is reversed as a mirror image. If there's an
even number of "A"s above then those mirrorings cancel out to be plain again.
This tree form is primarily of interest for "Digit Order Low to High" described below
since it gives points ordered clockwise down from the Y axis.
In "PQ Coordinates" below, with the default digits high to low, UArD also makes successive
steps across the row either horizontal or 45-degrees NE-SW.
In all cases the Gray coding is applied to N first, then the resulting digits are
interpreted either high to low (the default) or low to high ("LtoH" option).
FB Tree
Option "tree_type => "FB"" selects the Fibonacci boxes tree per
H. Lee Price, "The Pythagorean Tree: A New Species", 2008,
<http://arxiv.org/abs/0809.4324>
This tree is based on expressing triples in certain "Fibonacci boxes" with a box of four
values q',q,p,p' having p=q+q' and p'=p+q so each is the sum of the preceding two in a
fashion similar to the Fibonacci sequence. A box where p and q have no common factor
corresponds to a primitive triple. See "PQ Coordinates" and "FB Transformations" below.
tree_type => "FB"
Y=40 | 5
|
|
|
| 17
Y=24 | 4
|
| 8
|
Y=12 | 2 6
|
| 3
Y=4 | 1
|
+----------------------------------------------
X=3 X=15 x=21 X=35
For a given box three transformations can be applied to go to new boxes corresponding to
new primitive triples. This visits all and only primitive triples, but in a different
order to the UAD above.
The first point N=1 is again at X=3,Y=4, from which 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 A,B coordinates
+-> 5,12 --+-> 35,12
| +-> 11,60
|
| +-> 21,20
3,4 --+-> 15,8 --+-> 55,48
| +-> 39,80
|
| +-> 13,84
+-> 7,24 --+-> 63,16
+-> 15,112
UMT Tree
Option "tree_type =" "UMT"> is a third type made from a combination of "U" from Berggren,
"M2" from Price, and a third matrix T.
U +-> 7,24 A,B coordinates
+-> 5,12 --+-> 35,12
| +-> 65,72
|
| M2 +-> 33,56
3,4 --+-> 15,8 --+-> 55,48
| +-> 45,28
|
| T +-> 39,80
+-> 21,20 --+-> 91,60
+-> 105,88
The first "T" child 21,20 is the same as the "A" matrix, but it then differs at further
levels down. "T" twice is 105,88 which is not the same as "A" twice 119,120.
Digit Order Low to High
Option "digit_order => 'LtoH'" applies matrices using the ternary digits of N taken from
low to high. The points in each row are unchanged, as is the parent-child N numbering,
but the X,Y values are rearranged within the row.
The UAD matrices send points to disjoint regions and the effect of LtoH is to keep the
tree growing into those separate wedge regions. The arms grow roughly as follows
tree_type => "UAD", digit_order => "LtoH"
Y=80 | 6 UAD LtoH
| /
| /
Y=56 | / 7 10 9
| / / / /
| / / | / 8
| / _/ / / /
| / / / / /
Y=24 | 5 / / | / _/ __--11
| / / _/ |/_/ __--
Y=20 | / / / __3 __-- _____----12
| |/_/ __-- __--- ____-----
Y=12 | 2 __-- _/___---- ____13
| / __-- __-- _____-----
| /_--_____---4-----
Y=4 | 1---
|
+--------------------------------------------------
X=3 X=15 X=20 X=35 X=76
Notice the points of the second row N=5 to N=13 are almost clockwise down from the Y axis,
except N=8,9,10 go upwards. Those N=8,9,10 go upwards because the A matrix has a
reflection (its determinant is -1).
Option "tree_type => "UArD"" reverses the tree underneath each A, and that plus LtoH gives
A,B points going clockwise in each row. P,Q coordinates go clockwise too.
AC Coordinates
Option "coordinates => 'AC'" gives the A and C legs of each triple as X=A,Y=C.
coordinates => "AC"
85 | 122 10
|
|
73 | 6
|
65 | 11 40
61 | 41
|
| 7
|
|
41 | 14
| 13
35 |
| 3
25 | 5
|
17 | 4
13 | 2
|
Y=5 | 1
|
+-------------------------------------------
X=3 7 9 21 35 45 55 63 77
Since A<C the coordinates are X<Y all above the X=Y diagonal. The "D Repeatedly" triples
described above have C=A+2 so they are the points Y=X+2 just above the diagonal.
For the FB tree the set of points visited is the same, but with a different N numbering.
tree_type => "FB", coordinates => "AC"
85 | 11 35
|
|
73 | 9
|
65 | 23 12
61 | 7
|
| 17
|
|
41 | 5
| 6
35 |
| 8
25 | 4
|
17 | 3
13 | 2
|
Y=5 | 1
|
+-------------------------------------------
X=3 7 9 21 35 45 55 63 77
BC Coordinates
Option "coordinates => 'BC'" gives the B and C legs of each triple as X=B,Y=C. This is
the B=even and C=long legs of all primitive triples. This combination has points on
45-degree straight lines.
coordinates => "BC"
101 | 121
97 | 12
|
89 | 8
85 | 10 122
|
|
73 | 6
|
65 | 40 11
61 | 41
|
| 7
|
|
41 | 14
| 13
35 |
| 3
25 | 5
|
17 | 4
13 | 2
|
Y=5 | 1
|
+--------------------------------------------------
X=4 12 24 40 60 84
Since B<C the coordinates are X<Y above the X=Y leading diagonal. N=1,2,5,14,41,etc along
the X=Y-1 diagonal are the "U Repeatedly" triples described above which have C=B+1 and are
at the start of each tree row.
For the FB tree the set of points visited is the same, but with a different N numbering.
tree_type => "FB", coordinates => "BC"
101 | 15
97 | 50
|
89 | 10
85 | 35 11
|
|
73 | 9
|
65 | 12 23
61 | 7
|
| 17
|
|
41 | 5
| 6
35 |
| 8
25 | 4
|
17 | 3
13 | 2
|
Y=5 | 1
|
+----------------------------------------------
X=4 12 24 40 60 84
As seen from the diagrams, the B,C points fall on 45-degree straight lines going up from
X=Y-1. This occurs because a primitive triple A,B,C with A odd and B even can be written
A^2 = C^2 - B^2
= (C+B)*(C-B)
gcd(A,B)=1 means also gcd(C+B,C-B)=1 and so since C+B and C-B have no common factor they
must each be squares to give A^2. Call them s^2 and t^2,
C+B = s^2 and conversely C = (s^2 + t^2)/2
C-B = t^2 B = (s^2 - t^2)/2
s = odd integer s >= 3
t = odd integer s > t >= 1
with gcd(s,t)=1 so that gcd(C+B,C-B)=1
When t=1 this is C=(s^2+1)/2 and B=(s^2-1)/2 which is the "U"-repeated points at Y=X+1 for
each s. As t increases the B,C coordinate combination makes a line upwards at 45-degrees
from those t=1 positions,
C + B = s^2 anti-diagonal 45-degrees,
position along diagonal determined by t
All primitive triples start from a C=B+1 with C=(s^2+1)/2 half an odd square, and go up
from there. To ensure the triple is primitive must have gcd(s,t)=1. Values of t where
gcd(s,t)!=1 are gaps in the anti-diagonal lines.
PQ Coordinates
Primitive Pythagorean triples can be parameterized as follows for A odd and B even. This
is per Diophantus, and anonymous Arabic manuscript for constraining it to primitive
triples (Dickson's History of the Theory of Numbers).
A = P^2 - Q^2
B = 2*P*Q
C = P^2 + Q^2
with P > Q >= 1, one odd, one even, and no common factor
P = sqrt((C+A)/2)
Q = sqrt((C-A)/2)
The first P=2,Q=1 is the triple A=3,B=4,C=5.
Option "coordinates => 'PQ'" gives these as X=P,Y=Q, for either "tree_type". Because
P>Q>=1 the values fall in the eighth of the plane below the X=Y diagonal,
tree_type => "UAD", coordinates => "PQ"
10 | 9842
9 | 3281
8 | 1094 23
7 | 365 32
6 | 122 38
5 | 41 8
4 | 14 11 12 15
3 | 5 6 16
2 | 2 3 7 10 22
1 | 1 4 13 40 121
Y=0 |
+--------------------------------------------------------
X=0 1 2 3 4 5 6 7 8 9 10 11
The diagonal N=1,2,5,14,41,etc is P=Q+1 as per "U Repeatedly" above.
The one-to-one correspondence between P,Q and A,B means both tree types visit all P,Q
pairs, so all X,Y with no common factor and one odd one even. There's other ways to
iterate through such coprime pairs and any such method would generate Pythagorean triples
too, in a different order from the trees here.
The letters P and Q here are a little bit arbitrary. This parameterization is often
written m,n or u,v but don't want "n" to be confused that with N point numbering or "u" to
be confused with the U matrix.
SM Coordinates
Option "coordinates => 'SM'" gives the small and medium legs from each triple as
X=small,Y=medium. This is like "AB" except that if A>B then they're swapped to X=B,Y=A so
X<Y always. The effect is to mirror the AB points below the X=Y diagonal up to the upper
eighth,
coordinates => "SM"
91 | 16
84 | 122
| 8
| 10
72 | 12
|
|
60 | 41 40
| 11
55 | 6
|
| 7
40 | 14
|
35 | 13
|
24 | 5
21 | 3
|
12 | 2 4
|
Y=4 | 1
|
+----------------------------------------
X=3 8 20 33 48 60 65
SC Coordinates
Option "coordinates => 'SC'" gives the small leg and hypotenuse from each triple,
coordinates => "SC"
85 | 122 10
|
|
73 | 6
|
| 40 11
61 | 41
|
53 | 7
|
|
41 | 14
37 | 13
|
| 3
25 | 5
|
| 4
13 | 2
|
Y=5 | 1
|
+-----------------------------
X=3 8 20 33 48
The points are all X < 0.7*Y since with X as the smaller leg must have X^2 < Y^2/2 so
X < Y*1/sqrt(2).
MC Coordinates
Option "coordinates => 'MC'" gives the medium leg and hypotenuse from each triple,
coordinates => "MC"
65 | 11 40
61 | 41
|
53 | 7
|
|
41 | 14
37 | 13
|
29 | 3
25 | 5
|
17 | 4
13 | 2
|
Y=5 | 1
|
+-----------------------------------
X=4 15 24 35 40 56 63
The points are in a wedge 0.7*Y < X < Y. X is the bigger leg and X^2 > Y^2/2 so
X > Y*1/sqrt(2).
UAD Coordinates AB, AC, PQ -- Turn Right
In the UAD tree with coordinates AB, AC or PQ the path always turns to the right. For
example in AB coordinates at N=2 the path turns to the right to go towards N=3.
coordinates => "AB"
20 | 3 N X,Y
| -- ------
12 | 2 1 3,4
| 2 5,12
| 3 21,20
4 | 1
| turn towards the
+------------------------- right at N=2
3 5 21
This can be proved from the transformations applied to seven cases, a triplet U,A,D, then
four crossing a gap within a level, then two wrapping around at the end of a level. The
initial N=1,2,3 can be treated as a wrap-around from the end of depth=0 (the last case D
to U,A).
U triplet U,A,D
A
D
U.D^k.A crossing A,D to U
U.D^k.D across U->A gap
A.U^k.U k>=0
A.D^k.A crossing A,D to U
A.D^k.D across A->D gap
D.U^k.U k>=0
U.D^k.D crossing D to U,A
U.U^k.U across U->A gap
A.U^k.A k>=0
A.D^k.D crossing D to U,A
A.U^k.U across A->D gap
D.U^k.A k>=0
D^k .A wraparound A,D to U
D^k .D k>=0
U^(k+1).U
D^k wraparound D to U,A
U^k.U k>=0
U^k.A (k=0 is initial N=1,N=2,N=3 for none,U,A)
The powers U^k and D^k are an arbitrary number of descents U or D. In P,Q coordinates
these powers are
U^k P,Q -> (k+1)*P-k*Q, k*P-(k-1)*Q
D^k P,Q -> P+2k*Q, Q
For AC coordinates squaring to stretch to P^2,Q^2 doesn't change the turns. Then a rotate
by -45 degrees to A=P^2-Q^2, C=P^2+Q^2 also doesn't change the turns.
UAD Coordinates BC -- Turn Left
In the UAD tree with coordinates BC the path always turns to the left. For example in BC
coordinates at N=2 the path turns to the right to go towards N=3.
coordinates => "BC"
29 | 3 N X,Y
| -- ------
| 1 4,5
| 2 12,13
13 | 2 3 20,29
|
5 | 1 turn towards the
| left at N=2
+---------------
4 12 20
As per above A,C turns to the right, which squared is A^2,C^2 to the right too, which
equals C^2-B^2,C^2. Negating the X coordinate to B^2-C^2,C^2 mirrors to be a left turn
always, and addition shearing to X+Y,Y doesn't change that, giving B^2,C^2 always left and
so B,C always left.
FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
"$path = Math::PlanePath::PythagoreanTree->new ()"
"$path = Math::PlanePath::PythagoreanTree->new (tree_type => $str, coordinates => $str)"
Create and return a new path object. The "tree_type" option can be
"UAD" (the default)
"UArD" UAD with Gray code reflections
"FB"
"UMT"
The "coordinates" option can be
"AB" odd, even legs (the default)
"AC" odd leg, hypotenuse
"BC" even leg, hypotenuse
"PQ"
"SM" small, medium legs
"SC" small leg, hypotenuse
"MC" medium leg, hypotenuse
The "digit_order" option can be
"HtoL" high to low (the default)
"LtoH" low to high (the default)
"$n = $path->n_start()"
Return 1, the first N in the path.
"($x,$y) = $path->n_to_xy ($n)"
Return the X,Y coordinates of point number $n on the path. Points begin at 1 and if
"$n<1" then the return is an empty list.
"$n = $path->xy_to_n ($x,$y)"
Return the point number for coordinates "$x,$y". If there's nothing at "$x,$y" then
return "undef".
The return is "undef" if "$x,$y" is not a primitive Pythagorean triple, per the
"coordinates" option.
"$rsquared = $path->n_to_radius ($n)"
Return the radial distance R=sqrt(X^2+Y^2) of point $n. If there's no point $n then
return "undef".
For coordinates=AB or SM this is the hypotenuse C and therefore an integer, for
integer $n.
"($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.
Both trees go off into large X,Y coordinates while yet to finish values close to the
origin which means the N range for a rectangle can be quite large. For UAD $n_hi is
roughly "3**max(x/2)", or for FB smaller at roughly "3**log2(x)".
Descriptive Methods
"$x = $path->x_minimum()"
"$y = $path->y_minimum()"
Return the minimum X or Y occurring in the path. The value goes according to the
"coordinates" option,
coordinate minimum
---------- -------
A,S 3
B,M 4
C 5
P 2
Q 1
Tree Methods
Each point has 3 children, so the path is a complete ternary tree.
"@n_children = $path->tree_n_children($n)"
Return the three children of $n, or an empty list if "$n < 1" (ie. before the start of
the path).
This is simply "3*$n-1, 3*$n, 3*$n+1". This is appending an extra ternary digit 0, 1
or 2 to the mixed-radix form for N described above. Or staying all in ternary then
appending to N+1 rather than N and adjusting back.
"$num = $path->tree_n_num_children($n)"
Return 3, since every node has three children, or return "undef" if "$n<1" (ie. before
the start of the path).
"$n_parent = $path->tree_n_parent($n)"
Return the parent node of $n, or "undef" if "$n <= 1" (the top of the tree).
This is simply "floor(($n+1)/3)", reversing the "tree_n_children()" calculation above.
"$depth = $path->tree_n_to_depth($n)"
Return the depth of node $n, or "undef" if there's no point $n. The top of the tree
at N=1 is depth=0, then its children depth=1, etc.
The structure of the tree with 3 nodes per point means the depth is floor(log3(2N-1)),
so for example N=5 through N=13 all have depth=2.
"$n = $path->tree_depth_to_n($depth)"
"$n = $path->tree_depth_to_n_end($depth)"
Return the first or last N at tree level $depth in the path, or "undef" if nothing at
that depth or not a tree. The top of the tree is depth=0.
Tree Descriptive Methods
"$num = $path->tree_num_children_minimum()"
"$num = $path->tree_num_children_maximum()"
Return 3 since every node has 3 children, making that both the minimum and maximum.
"$bool = $path->tree_any_leaf()"
Return false, since there are no leaf nodes in the tree.
FORMULAS
UAD Matrices
Internally the code uses P,Q and calculates A,B at the end as necessary. The UAD
transformations in P,Q coordinates are
U P -> 2P-Q ( 2 -1 )
Q -> P ( 1 0 )
A P -> 2P+Q ( 2 1 )
Q -> P ( 1 0 )
D P -> P+2Q ( 1 2 )
Q -> Q unchanged ( 0 1 )
The advantage of P,Q for the calculation is that it's 2 values instead of 3. The
transformations can be written with the 2x2 matrices shown, but explicit steps are enough
for the code.
Repeatedly applying "U" gives
U 2P-Q, P
U^2 3P-2Q, 2P-Q
U^3 4P-3Q, 3P-2Q
...
U^k (k+1)P-kQ, kP-(k-1)Q
= P+k(P-Q), Q+k*(P-Q)
If there's a run of k many high zeros in the Nrem = N-Nrow position in the level then they
can be applied to the initial P=2,Q=1 as
U^k P=k+2, Q=k+1 start for k high zeros
FB Transformations
The FB tree is calculated in P,Q and converted to A,B at the end as necessary. Its three
transformations are
M1 P -> P+Q ( 1 1 )
Q -> 2Q ( 0 2 )
M2 P -> 2P ( 2 0 )
Q -> P-Q ( 1 -1 )
M3 P -> 2P ( 2 0 )
Q -> P+Q ( 1 1 )
Price's paper shows rearrangements of a set of four values q',q,p,p'. Just the p and q
are enough for the calculation. The set of four has some attractive geometric
interpretations though.
X,Y to N -- UAD
"xy_to_n()" works in P,Q coordinates. An A,B or other input is converted to P,Q per the
formulas in "PQ Coordinates" above. A P,Q point can be reversed up the UAD tree to its
parent point
if P > 3Q reverse "D" P -> P-2Q
digit=2 Q -> unchanged
if P > 2Q reverse "A" P -> Q
digit=1 Q -> P-2Q
otherwise reverse "U" P -> Q
digit=0 Q -> 2Q-P
This gives a ternary digit 2, 1, 0 respectively from low to high. Those plus a high "1"
bit make N. The number of steps is the "depth" level.
If at any stage P,Q doesn't satisfy P>Q>=1, one odd, the other even, then it means the
original point, however it was converted, was not a primitive triple. For a primitive
triple the endpoint is always P=2,Q=1.
The conditions P>3Q or P>2Q work because each matrix sends its parent P,Q to one of three
disjoint regions,
Q P=Q P=2Q P=3Q
| * U ---- A ++++++
| * ---- ++++++
| * ---- ++++++
| * ---- ++++++
| * ---- ++++++
| * ---- ++++++
| * ---- ++++++ D
| * ----++++++
| * ----++++
| ----++
|
+------------------------------------------------- P
So U is the upper wedge, A the middle, and D the lower. The parent P,Q can be anywhere in
P>Q>=1, the matrices always map to these regions.
X,Y to N -- FB
After converting to P,Q as necessary, a P,Q point can be reversed up the FB tree to its
parent
if P odd reverse M1 P -> P-Q
(Q even) Q -> Q/2
if P > 2Q reverse M2 P -> P/2
(P even) Q -> P/2 - Q
otherwise reverse M3 P -> P/2
(P even) Q -> Q - P/2
This is a little like the binary greatest common divisor algorithm, but designed for one
value odd and the other even. Like the UAD ascent above if at any stage P,Q doesn't
satisfy P>Q>=1, one odd, the other even, then the initial point wasn't a primitive triple.
The M1 reversal works because M1 sends any parent P,Q to a child which has P odd. All odd
P,Q comes from M1. The M2 and M3 always make children with P even. Those children are
divided between two disjoint regions above and below the line P=2Q.
Q P=Q P=2Q
| * M3 P=even ----
| * ----
| * ----
| * ----
| * ---- M2 P=even
| * ----
| * ----
| * ----
| * ---- M1 P=odd anywhere
| ----
|
+------------------------------------------------- P
X,Y to N -- UMT
After converting to P,Q as necessary, a P,Q point can be reversed up the UMT tree to its
parent
if P > 2Q reverse "U" P -> Q
digit=0 Q -> 2Q-P
if P even reverse "M2" P -> P/2
(Q odd) Q -> P/2 - Q
otherwise reverse "T" P -> P - 3 * Q/2
(Q even) Q -> Q/2
These reversals work because U sends any parent P,Q to a child P>2Q whereas the M2 and T
go below that line. M2 and T are distinguished by M2 giving P even whereas T gives P odd.
Q P=Q P=2Q
| * U ----
| * ----
| * ----
| * ----
| * ---- M2 for P=even
| * ---- T for P=odd
| * ----
| * ----
| * ----
| ----
|
+------------------------------------------------- P
Rectangle to N Range -- UAD
For the UAD tree, the smallest A,B within each level is found at the topmost "U" steps for
the smallest A or the bottom-most "D" steps for the smallest B. For example in the table
above of level=2 N=5..13 the smallest A is the top A=7,B=24, and the smallest B is in the
bottom A=35,B=12. In general
Amin = 2*level + 1
Bmin = 4*level
In P,Q coordinates the same topmost line is the smallest P and bottom-most the smallest Q.
The values are
Pmin = level+1
Qmin = 1
The fixed Q=1 arises from the way the "D" transformation sends Q->Q unchanged, so every
level includes a Q=1. This means if you ask what range of N is needed to cover all Q <
someQ then there isn't one, only a P < someP has an N to go up to.
Rectangle to N Range -- FB
For the FB tree, the smallest A,B within each level is found in the topmost two final
positions. For example in the table above of level=2 N=5..13 the smallest A is in the top
A=9,B=40, and the smallest B is in the next row A=35,B=12. In general,
Amin = 2^level + 1
Bmin = 2^level + 4
In P,Q coordinates a Q=1 is found in that second row which is the minimum B, and the
smallest P is found by taking M1 steps half-way then a M2 step, then M1 steps for the
balance. This is a slightly complicated
Pmin = / 3*2^(k-1) + 1 if even level = 2*k
\ 2^(k+1) + 1 if odd level = 2*k+1
Q = 1
The fixed Q=1 arises from the M1 steps giving
P = 2 + 1+2+4+8+...+2^(level-2)
= 2 + 2^(level-1) - 1
= 2^(level-1) + 1
Q = 2^(level-1)
followed by M2 step
Q -> P-Q
= 1
As for the UAD above this means small Q's always remain no matter how big N gets, only a P
range determines an N range.
OEIS
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include,
<http://oeis.org/A007051> (etc)
A007051 N start of depth=n, (3^n+1)/2, ie. tree_depth_to_n()
A003462 N end of depth=n-1, (3^n-1)/2, ie. tree_depth_to_n_end()
A000244 N of row middle line, 3^n
A058529 possible values taken by abs(A-B),
being integers with all prime factors == +/-1 mod 8
"U" repeatedly
A046092 coordinate B, 2n(n+1) = 4*triangular numbers
A099776 \ coordinate C, being 2n(n+1)+1
A001844 / which is the "centred squares"
"A" repeatedly
A046727 \ coordinate A
A084159 / "Pell oblongs"
A046729 coordinate B
A001653 coordinate C, numbers n where 2*n^2-1 is square
A000129 coordinate P and Q, the Pell numbers
A001652 coordinate S, the smaller leg
A046090 coordinate M, the bigger leg
"D" repeatedly
A000466 coordinate A, being 4*n^2-1 for n>=1
"M1" repeatedly
A028403 coordinate B, binary 10..010..000
A007582 coordinate B/4, binary 10..010..0
A085601 coordinate C, binary 10..010..001
"M2" repeatedly
A015249 \ coordinate A, binary 111000111000...
A084152 |
A084175 /
A054881 coordinate B, binary 1010..1010000..00
"M3" repeatedly
A106624 coordinate P,Q pairs, 2^k-1,2^k
"T" repeatedly
A134057 coordinate A, binomial(2^n-1,2)
binary 111..11101000..0001
A093357 coordinate B, binary 10111..111000..000
A052940 \
A055010 | coordinate P, 3*2^n-1
A083329 | binary 10111..111
A153893 /
SEE ALSO
Math::PlanePath, Math::PlanePath::Hypot, Math::PlanePath::RationalsTree,
Math::PlanePath::CoprimeColumns
HOME PAGE
<http://user42.tuxfamily.org/math-planepath/index.html>
LICENSE
Copyright 2011, 2012, 2013 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/>.