Math::...anTree(3pm)
✨ Math::PlanePath::PythagoreanTree ✨
okay bestie, so this is a User Contributed Perl Documentation page for Math::PlanePath::PythagoreanTree(3pm), and it's literally the blueprint for generating primitive Pythagorean triples with a tree walk. grab a snack, we're doing math 💅
🌸 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 💖
so basically this path enumerates primitive Pythagorean triples by doing a breadth-first traversal of one of three ternary trees:
"UAD"— Berggren, Barning, Hall, and others"FB"— Firstov and Price"UMT"— Firstov
Every X,Y point is a pair of integer A,B sides of a right triangle 🫶 and the points are "primitive" in the sense that A and B have no common factor. (like, no shared divisor at all, they're giving coprime energy)
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 A odd and B even, periodt.
the trees get traversed breadth-first and they 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 more properties, it's at <http://user42.tuxfamily.org/triples/index.html> ✨
🎀 UAD Tree 🎀
the UAD tree is by Berggren (1934) and then later, independently, by Barning (1963), Hall (1970), and other authors 👑 it uses three matrices U, A and D which you can multiply onto an existing primitive triple to form three further new primitive triples.
tree_type => "UAD" (the default, bestie, you don't even have to ask)
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 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 that well-known triple everyone knows:
3^2 + 4^2 = 5^2from it, three further points N=2, N=3 and N=4 are derived, then three more from each of those, etc:
tree_type => "UAD" coordinates A,B
______________ 3,4 _____________
/ | \
5,12 21,20 15,8
/ | \ / | \ / | \
7,24 55,48 45,28 39,80 119,120 77,36 33,56 65,72 35,12
rows depth = 0 N=1
depth = 1 N=2..4
depth = 2 N=5..13
depth = 3 N=14..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
= 1, 2, 5, 14, 41, 122, 365, ... (A007051)the level numbering is like a mixed-radix representation of N where the high digit is binary (so always 1, no notes) and the digits below are ternary 💜
+--------+---------+---------+-- --+---------+
N = | binary | ternary | ternary | ... | ternary |
+--------+---------+---------+-- --+---------+
1 0,1,2 0,1,2 0,1,2the number of ternary digits is the "depth" and their value without the high binary 1 is the position in the row ⭐
🌈 U Repeatedly 🌈
taking the upper "U" matrix repeatedly gives
3.4 -> 5,12 -> 7,24 -> 9,40 -> etcwith C=B+1 and A the odd numbers. these are the first of each level, so at Nrow described above 👑 and 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 (Liber Quadratorum) 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=12the geometric interpretation is that an existing square of side B gets 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 👀
💜 A Repeatedly 💜
taking the middle "A" matrix repeatedly gives
3,4 -> 21,20 -> 119,120 -> 697,696 -> etc A,B legswhich are the triples with legs A,B differing by 1 and so just above and 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 A,B legswhich 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 >= 2 for primitives
B = 2*k
C = k^2 + 1 so C=A+2when k is even these are primitive 🌸 but if k is odd then A and B are both even, i.e. 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().
🌟 UArD Tree 🌟
option tree_type => "UArD" varies the UAD tree by applying a left-right reflection under each "A" matrix. the result is ternary reflected Gray code order. the 3 children under each node are unchanged, just their order 💫
tree_type => "UArD" coordinates A,B
______________ 3,4 _____________
/ | \
5,12 21,20 15,8
/ | \ / | \ / | \
7,24 55,48 45,28 77,36 119,120 39,80 33,56 65,72 35,12notice 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 mirrored left <-> right. 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 each row of points in order 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 a tree independently found by:
- V. E. Firstov, "A Special Matrix Transformation Semigroup of Primitive Pairs and the Genealogy of Pythagorean Triples", Matematicheskie Zametki, 2008, volume 84, number 2, pages 281-299 (in Russian), and Mathematical Notes, 2008, volume 84, number 2, pages 263-279 (in English)
- H. Lee Price, "The Pythagorean Tree: A New Species", 2008,
<http://arxiv.org/abs/0809.4324>(version 2)
Firstov finds this tree by semigroup transformations. Price finds it by 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=35for 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 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.
tree_type => "FB" coordinates A,B
______________ 3,4 _____________
/ | \
5,12 15,8 7,24
/ | \ / | \ / | \
9,40 35,12 11,60 21,20 55,48 39,80 13,84 63,16 15,112🎀 UMT Tree 🎀
option tree_type => "UMT" is a third tree type by Firstov (reference above). it is matrices U, M2, and a new third T = M1*D ✨
tree_type => "UMT" coordinates A,B children U,M2,T
______________ 3,4 _____________
/ | \
5,12 15,8 21,20
/ | \ / | \ / | \
7,24 35,12 65,72 33,56 55,48 45,28 39,80 91,60 105,88the first "T" child 21,20 is the same as the "A" matrix, but it differs at further levels down 😱 for example "T" twice is 105,88 (bottom most in the diagram) 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 yeet points into completely disjoint regions, and what LtoH does is keep the tree growing out into those separate wedge-y areas. The arms grow roughly like this:
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=76So like, notice how the points in the second row, N=5 to N=13, are almost going clockwise down from the Y axis… except N=8, 9, and 10, which go upwards. Why? Because the A matrix has a reflection, bestie — its determinant is -1. That's it, that's the reason. 💅
And then tree_type => "UArD" reverses the tree underneath each A, and that plus LtoH gives you A,B points going clockwise in each row. P,Q coordinates likewise go clockwise. periodt.
🎀 AC Coordinates 🎀
coordinates => 'AC' hands you the A and C legs of each triple as X=A, Y=C. Obsessed.
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 77Since A<C, the coordinates are all X<Y and they all sit above the X=Y diagonal. And the "D Repeatedly" triples we were just talking about? They have C=A+2, so they're literally the points Y=X+2 floating right above the diagonal. iconic.
For the FB tree, the set of points visited is the same (of course), but you get 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 💜
coordinates => 'BC' gives you 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, and this combination has points sitting on 45-degree straight lines. main character energy fr fr.
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 84Since B<C, the coordinates are X<Y, above the X=Y leading diagonal. And the points N=1,2,5,14,41, etc., along the X=Y-1 diagonal are the "U Repeatedly" triples we described above — they have C=B+1 and they're at the start of each tree row. 🌸
For the FB tree, the set of points visited is the same, obviously, but 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 84As you can see in the diagrams, B,C points fall on 45-degree straight lines going up from X=Y-1. This happens because a primitive triple A,B,C with A odd and B even can be written as
A^2 = C^2 - B^2
= (C+B)*(C-B)Then 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)=1When 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 tAll primitive triples start from a C=B+1 with C=(s^2+1)/2 half an odd square, and go up from there. And to make sure the triple is primitive, you must have gcd(s,t)=1. Values of t where gcd(s,t)!=1 are gaps in the anti-diagonal lines. no cap.
✨ PQ Coordinates ✨
Primitive Pythagorean triples can be parameterized like this, for A odd and B even. This is per Euclid, Diophantus, and an anonymous Arabic manuscript for constraining it to primitive triples (Dickson's History of the Theory of Numbers, start of chapter IV).
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. baby's first triple 🥹
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 11The 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 all 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 honestly any such method would generate Pythagorean triples too — just in a different order from the trees here.
The letters P and Q here are a little bit arbitrary, ngl. This parameterization is often written m,n or u,v, but we don't want "n" getting confused with the N point numbering, or "u" getting confused with the U matrix (leg "A" is already way too close to matrix "A"!). 🙈
🦋 SM Coordinates 🦋
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 into the upper half quadrant:
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 🍓
coordinates => 'SC' gives the small leg and the 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 48The points are all X < sqrt(2)*Y, since with X as the smaller leg you must have X^2 < Y^2/2, so X < Y*1/sqrt(2). math is mathing 💅
🌈 MC Coordinates 🌈
coordinates => 'MC' gives the medium leg and the 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 63So yeah, the points are in a wedge sqrt(2)*Y < X < Y. X is the bigger leg, and X^2 > Y^2/2 so X > Y*1/sqrt(2). math is mathing 💅
🦋 UAD Coordinates AB, AC, PQ -- Turn Right 🦋
Okay bestie so in the UAD tree, with coordinates AB, AC or PQ, the path always turns to the right. Like, always always. For example in AB coordinates at N=2, the path turns right to head 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 21This is provable 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. And the initial N=1,2,3 can be treated as a wrap-around from the end of depth=0 (that's the last case, D to U,A). Slay, the proof is giving structure 🎀
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 just an arbitrary number of descents U or D. And in P,Q coordinates, those powers look like this:
U^k P,Q -> (k+1)*P-k*Q, k*P-(k-1)*Q
D^k P,Q -> P+2k*Q, QFor 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. iconic, honestly 🌈
🌸 UAD Coordinates BC -- Turn Left 🌸
And over 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. (Yes the original says "right" there. Keeping it exactly as the docs do — no cap, character for character 🙈)
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 20As per above, A,C turns to the right, and squared that's A^2,C^2 turning right too, which equals C^2-B^2,C^2. Negating the X coordinate to B^2-C^2,C^2 mirrors it 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 therefore B,C always left. the way that logic just chains ✨
✨ FUNCTIONS ✨
Heads up bestie, go peep "FUNCTIONS" in Math::PlanePath for the behaviour that's common to all path classes. 💜
$path = Math::PlanePath::PythagoreanTree->new ()$path = Math::PlanePath::PythagoreanTree->new (tree_type => $str, coordinates => $str)
Create and return a brand new path object, as a treat 🫶
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, hypotenuseThe digit_order option can be:
"HtoL" high to low (the default)
"LtoH" low to high (the default)Not me noticing both of those say "(the default)" 😭 that's literally what the docs say so that's literally what you're getting. No editing, no notes. 💀
$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<1then the return is an empty list. ngl that's it, that's the whole vibe.$n = $path->xy_to_n ($x,$y)— Return the point number for coordinates$x,$y. If there's nothing at$x,$ythen returnundef.
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 returnundef.
For coordinates=AB or SM, this is the hypotenuse C and therefore an integer, for integer $n. periodt 💅
($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). huge range energy, lowkey terrifying 😭
🔍 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 🌳
Every point has 3 children, so the path is a complete ternary tree. obsessed with the symmetry fr fr 🎀
@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. That's appending an extra ternary digit 0, 1 or 2 to the mixed-radix form for N described above. Or, staying all in ternary, 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 returnundefif$n<1(ie. before the start of the path).$n_parent = $path->tree_n_parent($n)— Return the parent node of $n, orundefif$n <= 1(the top of the tree).
This is simply floor(($n+1)/3), reversing the tree_n_children() calculation above. it's giving symmetry 👑
$depth = $path->tree_n_to_depth($n)— Return the depth of node $n, orundefif there's no point $n. The top of the tree at N=1 is depth=0, then its children are 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 the maximum. queen behaviour, no range 💅
$bool = $path->tree_any_leaf()— Return false, since there are no leaf nodes in the tree. every node's a parent, no leaves, main character energy only 🌸
✨ FORMULAS ✨
okay bestie, this is where the math starts mathing. 💅
🧮 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. P,Q 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-PThis 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
| * ----++++++
| * ----++++
| ----++
|
+------------------------------------------------- PSo 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/2This 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 come 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/2These 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*levelIn P,Q coordinates the same topmost line is the smallest P and bottom-most the smallest Q. The values are
Pmin = level+1
Qmin = 1The 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 + 4In 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 = 1The 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
= 1As 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^nA058529— possible values taken byabs(A-B), being integers with all prime factors== +/-1 mod 8
UAD Tree HtoL
A321768— leg AA321769— leg BA321770— hypot CA321782— P (and the same for LtoH)A321783— QA321784— P+QA321785— P-Q
UAD Tree
A001542— row total p (even Pells)A001653— row total q (odd Pells)A001541— row total p + total qA002315— row total p - total q
"U" repeatedly
A046092— leg B,2n(n+1) = 4*triangular numbersA099776—\hypot C, being2n(n+1)+1A001844—/which is the "centred squares"
"A" repeatedly
A046727—\leg AA084159—/"Pell oblongs"A046729— leg BA001653— hypot C, numbers n where2*n^2-1is squareA000129— P and Q, the Pell numbersA001652— leg S, the smallerA046090— leg M, the bigger
"D" repeatedly
A000466— leg A, being4*n^2-1forn>=1
"M1" repeatedly
A028403— leg B, binary10..010..000A007582— leg B/4, binary10..010..0A085601— hypot C, binary10..010..001
"M2" repeatedly
A015249—\leg A, binary111000111000...A084152—|A084175—/A054881— leg B, binary1010..1010000..00
"M3" repeatedly
A106624— P,Q pairs,2^k-1,2^k
"T" repeatedly
A134057— leg A,binomial(2^n-1,2)binary111..11101000..0001A093357— leg B, binary10111..111000..000A052940—\A055010—|P,3*2^n-1A083329—|binary10111..111A153893—/
👀 SEE ALSO 👀
Math::PlanePathMath::PlanePath::HypotMath::PlanePath::RationalsTreeMath::PlanePath::CoprimeColumns
🏠 HOME PAGE 🏠
<http://user42.tuxfamily.org/math-planepath/index.html>
📜 LICENSE 📜
Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 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/>.
💖 And that's the whole manual, bestie! This iconic page is fromperl v5.32.0, dated2021-01-23, and it's theMath::...anTree(3pm)manual. Stay slay, stay recursive, and may your triples always be primitive. 💅✨
📦 where this page comes from
- debian bookworm: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- debian trixie: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- ubuntu jammy: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- ubuntu noble: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- ubuntu resolute: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- ubuntu stonking: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- 💖 girlified by deepseek-ai/DeepSeek-V4.1-Flash on : a language model's rewrite of the original, under its terms