1Math::PlanePath::PythagUosreeranCTorneter(i3b)uted PerlMDaotchu:m:ePnltaanteiPoanth::PythagoreanTree(3)
2
6 Math::PlanePath::PythagoreanTree -- primitive Pythagorean triples by
7 tree
8
10 use Math::PlanePath::PythagoreanTree;
11 my $path = Math::PlanePath::PythagoreanTree->new
12 (tree_type => 'UAD',
13 coordinates => 'AB');
14 my ($x, $y) = $path->n_to_xy (123);
15
17 This path enumerates primitive Pythagorean triples by a breadth-first
18 traversal of one of three ternary trees,
19 "UAD" Berggren, Barning, Hall, and others
21 "FB" Firstov and Price
22 "UMT" Firstov
23 Each X,Y point is a pair of integer A,B sides of a right triangle. The
25 points are "primitive" in the sense that the sense that A and B have no
26 common factor.
27 A^2 + B^2 = C^2 gcd(A,B) = 1, no common factor
29 X=A, Y=B
30 ^ * ^
32 / /| | right triangle
33 C / | B A side odd
34 / / | | B side even
35 v *---* v C hypotenuse
36 (all integers)
37 <-A->
38 A primitive triple always has one of A,B odd and the other even. The
40 trees here have A odd and B even.
41 The trees are traversed breadth-first and tend to go out to rather
43 large A,B values while yet to complete smaller ones. The UAD tree goes
44 out further than the FB. See the author's mathematical write-up for
45 more properties.
46 <http://user42.tuxfamily.org/triples/index.html>
48 UAD Tree
50 The UAD tree by Berggren (1934) and later independently by Barning
51 (1963), Hall (1970), and other authors, uses three matrices U, A and D
52 which can be multiplied onto an existing primitive triple to form three
53 further new primitive triples.
54 tree_type => "UAD" (the default)
56 Y=40 | 14
58 |
59 |
60 |
61 | 7
62 Y=24 | 5
63 |
64 Y=20 | 3
65 |
66 Y=12 | 2 13
67 |
68 | 4
69 Y=4 | 1
70 |
71 +--------------------------------------------------
72 X=3 X=15 X=20 X=35 X=45
73 The UAD matrices are
75 / 1 -2 2 \ / 1 2 2 \ / -1 2 2 \
77 U = | 2 -1 2 | A = | 2 1 2 | D = | -2 1 2 |
78 \ 2 -2 3 / \ 2 2 3 / \ -2 2 3 /
79 They're multiplied on the right of an (A,B,C) column vector, for
81 example
82 / 3 \ / 5 \
84 U * | 4 | = | 12 |
85 \ 5 / \ 13 /
86 The starting point is N=1 at X=3,Y=4 which is the well-known triple
88 3^2 + 4^2 = 5^2
90 From it three further points N=2, N=3 and N=4 are derived, then three
92 more from each of those, etc,
93 tree_type => "UAD" coordinates A,B
95 ______________ 3,4 _____________
97 / | \
98 5,12 21,20 15,8
99 / | \ / | \ / | \
100 7,24 55,48 45,28 39,80 119,120 77,36 33,56 65,72 35,12
101 rows depth = 0 N=1
103 depth = 1 N=2..4
104 depth = 2 N=5..13
105 depth = 3 N=14..
106 Counting N=1 as depth=0, each level has 3^depth many points and the
108 first N of a level ("tree_depth_to_n()") is at
109 Nrow = 1 + (1 + 3 + 3^2 + ... + 3^(depth-1))
111 = (3^depth + 1) / 2
112 = 1, 2, 5, 14, 41, 122, 365, ... (A007051)
113 The level numbering is like a mixed-radix representation of N where the
115 high digit is binary (so always 1) and the digits below are ternary.
116 +--------+---------+---------+-- --+---------+
118 N = | binary | ternary | ternary | ... | ternary |
119 +--------+---------+---------+-- --+---------+
120 1 0,1,2 0,1,2 0,1,2
121 The number of ternary digits is the "depth" and their value without the
123 high binary 1 is the position in the row.
124 U Repeatedly
126 Taking the upper "U" matrix repeatedly gives
127 3.4 -> 5,12 -> 7,24 -> 9,40 -> etc
129 with C=B+1 and A the odd numbers. These are the first of each level so
131 at Nrow described above. The resulting triples are a sequence known to
132 Pythagoras (Dickson's History of the Theory of Numbers, start of
133 chapter IV).
134 A = any odd integer, so A^2 any odd square
136 B = (A^2-1)/2
137 C = (A^2+1)/2
138 / A^2-1 \ / A^2+1 \
140 A^2 + | ------ |^2 = | ----- |^2
141 \ 2 / \ 2 /
142 This is also described by Fibonacci (Liber Quadratorum) in terms of
144 sums of odd numbers
145 s = any odd square = A^2
147 B^2 = 1 + 3 + 5 + ... + s-2 = ((s-1)/2)^2
148 C^2 = 1 + 3 + 5 + ... + s-2 + s = ((s+1)/2)^2
149 so C^2 = A^2 + B^2
150 eg. s=25=A^2 B^2=((25-1)/2)^2=144 so A=5,B=12
152 The geometric interpretation is that an existing square of side B is
154 extended by a "gnomon" around two sides making a new larger square of
155 side C=B+1. The length of the gnomon is odd and when it's an odd
156 square then the new total area is the sum of two squares.
157 ****gnomon******* gnomon length an odd square = A^2
159 +-------------+ *
160 | | * so new bigger square area
161 | square | * C^2 = A^2 + B^2
162 | with side B | *
163 | | *
164 +-------------+ *
165 See Math::PlanePath::Corner for a path following such gnomons.
167 A Repeatedly
169 Taking the middle "A" matrix repeatedly gives
170 3,4 -> 21,20 -> 119,120 -> 697,696 -> etc A,B legs
172 which are the triples with legs A,B differing by 1 and so just above
174 and below the X=Y leading diagonal. The N values are 1,3,9,27,etc =
175 3^depth.
176 D Repeatedly
178 Taking the lower "D" matrix repeatedly gives
179 3,4 -> 15,8 -> 35,12 -> 63,16 -> etc A,B legs
181 which is the primitives among a sequence of triples known to the
183 ancients (Dickson's History of the Theory of Numbers, start of chapter
184 IV),
185 A = k^2 - 1 k even >= 2 for primitives
187 B = 2*k
188 C = k^2 + 1 so C=A+2
189 When k is even these are primitive. If k is odd then A and B are both
191 even, ie. a common factor of 2, so not primitive. These points are the
192 last of each level, so at N=(3^(depth+1)-1)/2 which is
193 "tree_depth_to_n_end()".
194 UArD Tree
196 Option "tree_type => "UArD"" varies the UAD tree by applying a left-
197 right reflection under each "A" matrix. The result is ternary
198 reflected Gray code order. The 3 children under each node are
199 unchanged, just their order.
200 tree_type => "UArD" coordinates A,B
202 ______________ 3,4 _____________
204 / | \
205 5,12 21,20 15,8
206 / | \ / | \ / | \
207 7,24 55,48 45,28 77,36 119,120 39,80 33,56 65,72 35,12
208 Notice the middle points 77,36 and 39,80 are swapped relative to the
210 UAD shown above. In general, the whole tree underneath an "A" is
211 mirrored left <->right. If there's an even number of "A"s above then
212 those mirrorings cancel out to be plain again.
213 This tree form is primarily of interest for "Digit Order Low to High"
215 described below since it gives each row of points in order clockwise
216 down from the Y axis.
217 In "PQ Coordinates" below, with the default digits high to low, UArD
219 also makes successive steps across the row either horizontal or
220 45-degrees NE-SW.
221 In all cases, the Gray coding is applied to N first, then the resulting
223 digits are interpreted either high to low (the default) or low to high
224 ("LtoH" option).
225 FB Tree
227 Option "tree_type => "FB"" selects a tree independently by
228 V. E. Firstov, "A Special Matrix Transformation Semigroup of
230 Primitive Pairs and the Genealogy of Pythagorean Triples",
231 Matematicheskie Zametki, 2008, volume 84, number 2, pages 281-299
232 (in Russian), and Mathematical Notes, 2008, volume 84, number 2,
233 pages 263-279 (in English)
234 H. Lee Price, "The Pythagorean Tree: A New Species", 2008,
236 <http://arxiv.org/abs/0809.4324> (version 2)
237 Firstov finds this tree by semigroup transformations. Price finds it
239 by expressing triples in certain "Fibonacci boxes" with a box of four
240 values q',q,p,p' having p=q+q' and p'=p+q so each is the sum of the
241 preceding two in a fashion similar to the Fibonacci sequence. A box
242 where p and q have no common factor corresponds to a primitive triple.
243 See "PQ Coordinates" and "FB Transformations" below.
244 tree_type => "FB"
246 Y=40 | 5
248 |
249 |
250 |
251 | 17
252 Y=24 | 4
253 |
254 | 8
255 |
256 Y=12 | 2 6
257 |
258 | 3
259 Y=4 | 1
260 |
261 +----------------------------------------------
262 X=3 X=15 x=21 X=35
263 For a given box, three transformations can be applied to go to new
265 boxes corresponding to new primitive triples. This visits all and only
266 primitive triples, but in a different order to UAD above.
267 The first point N=1 is again at X=3,Y=4, from which three further
269 points N=2,3,4 are derived, then three more from each of those, etc.
270 tree_type => "FB" coordinates A,B
272 ______________ 3,4 _____________
274 / | \
275 5,12 15,8 7,24
276 / | \ / | \ / | \
277 9,40 35,12 11,60 21,20 55,48 39,80 13,84 63,16 15,112
278 UMT Tree
280 Option "tree_type => "UMT"" is a third tree type by Firstov (reference
281 above). It is matrices U, M2, and a new third T = M1*D.
282 tree_type => "UMT" coordinates A,B children
284 U,M2,T
285 ______________ 3,4 _____________
286 / | \
287 5,12 15,8 21,20
288 / | \ / | \ / | \
289 7,24 35,12 65,72 33,56 55,48 45,28 39,80 91,60 105,88
290 The first "T" child 21,20 is the same as the "A" matrix, but it differs
292 at further levels down. For example "T" twice is 105,88 (bottom most
293 in the diagram) which is not the same as "A" twice 119,120.
294 Digit Order Low to High
296 Option "digit_order => 'LtoH'" applies matrices using the ternary
297 digits of N taken from low to high. The points in each row are
298 unchanged, as is the parent-child N numbering, but the X,Y values are
299 rearranged within the row.
300 The UAD matrices send points to disjoint regions and the effect of LtoH
302 is to keep the tree growing into those separate wedge regions. The
303 arms grow roughly as follows
304 tree_type => "UAD", digit_order => "LtoH"
306 Y=80 | 6 UAD LtoH
308 | /
309 | /
310 Y=56 | / 7 10 9
311 | / / / /
312 | / / | / 8
313 | / _/ / / /
314 | / / / / /
315 Y=24 | 5 / / | / _/ __--11
316 | / / _/ |/_/ __--
317 Y=20 | / / / __3 __-- _____----12
318 | |/_/ __-- __--- ____-----
319 Y=12 | 2 __-- _/___---- ____13
320 | / __-- __-- _____-----
321 | /_--_____---4-----
322 Y=4 | 1---
323 |
324 +--------------------------------------------------
325 X=3 X=15 X=20 X=35 X=76
326 Notice the points of the second row N=5 to N=13 are almost clockwise
328 down from the Y axis, except N=8,9,10 go upwards. Those N=8,9,10 go
329 upwards because the A matrix has a reflection (its determinant is -1).
330 Option "tree_type => "UArD"" reverses the tree underneath each A, and
332 that plus LtoH gives A,B points going clockwise in each row. P,Q
333 coordinates likewise go clockwise.
334 AC Coordinates
336 Option "coordinates => 'AC'" gives the A and C legs of each triple as
337 X=A,Y=C.
338 coordinates => "AC"
340 85 | 122 10
342 |
343 |
344 73 | 6
345 |
346 65 | 11 40
347 61 | 41
348 |
349 | 7
350 |
351 |
352 41 | 14
353 | 13
354 35 |
355 | 3
356 25 | 5
357 |
358 17 | 4
359 13 | 2
360 |
361 Y=5 | 1
362 |
363 +-------------------------------------------
364 X=3 7 9 21 35 45 55 63 77
365 Since A<C, the coordinates are X<Y all above the X=Y diagonal. The "D
367 Repeatedly" triples described above have C=A+2 so they are the points
368 Y=X+2 just above the diagonal.
369 For the FB tree the set of points visited is the same (of course), but
371 a different N numbering.
372 tree_type => "FB", coordinates => "AC"
374 85 | 11 35
376 |
377 |
378 73 | 9
379 |
380 65 | 23 12
381 61 | 7
382 |
383 | 17
384 |
385 |
386 41 | 5
387 | 6
388 35 |
389 | 8
390 25 | 4
391 |
392 17 | 3
393 13 | 2
394 |
395 Y=5 | 1
396 |
397 +-------------------------------------------
398 X=3 7 9 21 35 45 55 63 77
399 BC Coordinates
401 Option "coordinates => 'BC'" gives the B and C legs of each triple as
402 X=B,Y=C. This is the B=even and C=long legs of all primitive triples.
403 This combination has points on 45-degree straight lines.
404 coordinates => "BC"
406 101 | 121
408 97 | 12
409 |
410 89 | 8
411 85 | 10 122
412 |
413 |
414 73 | 6
415 |
416 65 | 40 11
417 61 | 41
418 |
419 | 7
420 |
421 |
422 41 | 14
423 | 13
424 35 |
425 | 3
426 25 | 5
427 |
428 17 | 4
429 13 | 2
430 |
431 Y=5 | 1
432 |
433 +--------------------------------------------------
434 X=4 12 24 40 60 84
435 Since B<C, the coordinates are X<Y above the X=Y leading diagonal.
437 N=1,2,5,14,41,etc along the X=Y-1 diagonal are the "U Repeatedly"
438 triples described above which have C=B+1 and are at the start of each
439 tree row.
440 For the FB tree, the set of points visited is the same of course, but a
442 different N numbering.
443 tree_type => "FB", coordinates => "BC"
445 101 | 15
447 97 | 50
448 |
449 89 | 10
450 85 | 35 11
451 |
452 |
453 73 | 9
454 |
455 65 | 12 23
456 61 | 7
457 |
458 | 17
459 |
460 |
461 41 | 5
462 | 6
463 35 |
464 | 8
465 25 | 4
466 |
467 17 | 3
468 13 | 2
469 |
470 Y=5 | 1
471 |
472 +----------------------------------------------
473 X=4 12 24 40 60 84
474 As seen in the diagrams, B,C points fall on 45-degree straight lines
476 going up from X=Y-1. This occurs because a primitive triple A,B,C with
477 A odd and B even can be written
478 A^2 = C^2 - B^2
480 = (C+B)*(C-B)
481 Then gcd(A,B)=1 means also gcd(C+B,C-B)=1 and so since C+B and C-B have
483 no common factor they must each be squares to give A^2. Call them s^2
484 and t^2,
485 C+B = s^2 and conversely C = (s^2 + t^2)/2
487 C-B = t^2 B = (s^2 - t^2)/2
488 s = odd integer s >= 3
490 t = odd integer s > t >= 1
491 with gcd(s,t)=1 so that gcd(C+B,C-B)=1
492 When t=1, this is C=(s^2+1)/2 and B=(s^2-1)/2 which is the "U"-repeated
494 points at Y=X+1 for each s. As t increases, the B,C coordinate
495 combination makes a line upwards at 45-degrees from those t=1
496 positions,
497 C + B = s^2 anti-diagonal 45-degrees,
499 position along diagonal determined by t
500 All primitive triples start from a C=B+1 with C=(s^2+1)/2 half an odd
502 square, and go up from there. To ensure the triple is primitive, must
503 have gcd(s,t)=1. Values of t where gcd(s,t)!=1 are gaps in the anti-
504 diagonal lines.
505 PQ Coordinates
507 Primitive Pythagorean triples can be parameterized as follows for A odd
508 and B even. This is per Euclid, Diophantus, and anonymous Arabic
509 manuscript for constraining it to primitive triples (Dickson's History
510 of the Theory of Numbers, start of chapter IV).
511 A = P^2 - Q^2
513 B = 2*P*Q
514 C = P^2 + Q^2
515 with P > Q >= 1, one odd, one even, and no common factor
516 P = sqrt((C+A)/2)
518 Q = sqrt((C-A)/2)
519 The first P=2,Q=1 is the triple A=3,B=4,C=5.
521 Option "coordinates => 'PQ'" gives these as X=P,Y=Q, for either
523 "tree_type". Because P>Q>=1 the values fall in the eighth of the plane
524 below the X=Y diagonal,
525 tree_type => "UAD", coordinates => "PQ"
527 10 | 9842
529 9 | 3281
530 8 | 1094 23
531 7 | 365 32
532 6 | 122 38
533 5 | 41 8
534 4 | 14 11 12 15
535 3 | 5 6 16
536 2 | 2 3 7 10 22
537 1 | 1 4 13 40 121
538 Y=0 |
539 +--------------------------------------------------------
540 X=0 1 2 3 4 5 6 7 8 9 10 11
541 The diagonal N=1,2,5,14,41,etc is P=Q+1 as per "U Repeatedly" above.
543 The one-to-one correspondence between P,Q and A,B means all tree types
545 visit all P,Q pairs, so all X,Y with no common factor and one odd one
546 even. There's other ways to iterate through such coprime pairs and any
547 such method would generate Pythagorean triples too, in a different
548 order from the trees here.
549 The letters P and Q here are a little bit arbitrary. This
551 parameterization is often written m,n or u,v but don't want "n" to be
552 confused that with N point numbering or "u" to be confused with the U
553 matrix (leg "A" is already too close to matrix "A"!).
554 SM Coordinates
556 Option "coordinates => 'SM'" gives the small and medium legs from each
557 triple as X=small,Y=medium. This is like "AB" except that if A>B then
558 they're swapped to X=B,Y=A so X<Y always. The effect is to mirror the
559 AB points below the X=Y diagonal up to the upper half quadrant,
560 coordinates => "SM"
562 91 | 16
564 84 | 122
565 | 8
566 | 10
567 72 | 12
568 |
569 |
570 60 | 41 40
571 | 11
572 55 | 6
573 |
574 | 7
575 40 | 14
576 |
577 35 | 13
578 |
579 24 | 5
580 21 | 3
581 |
582 12 | 2 4
583 |
584 Y=4 | 1
585 |
586 +----------------------------------------
587 X=3 8 20 33 48 60 65
588 SC Coordinates
590 Option "coordinates => 'SC'" gives the small leg and hypotenuse from
591 each triple,
592 coordinates => "SC"
594 85 | 122 10
596 |
597 |
598 73 | 6
599 |
600 | 40 11
601 61 | 41
602 |
603 53 | 7
604 |
605 |
606 41 | 14
607 37 | 13
608 |
609 | 3
610 25 | 5
611 |
612 | 4
613 13 | 2
614 |
615 Y=5 | 1
616 |
617 +-----------------------------
618 X=3 8 20 33 48
619 The points are all X < sqrt(2)*Y since with X as the smaller leg must
621 have X^2 < Y^2/2 so X < Y*1/sqrt(2).
622 MC Coordinates
624 Option "coordinates => 'MC'" gives the medium leg and hypotenuse from
625 each triple,
626 coordinates => "MC"
628 65 | 11 40
630 61 | 41
631 |
632 53 | 7
633 |
634 |
635 41 | 14
636 37 | 13
637 |
638 29 | 3
639 25 | 5
640 |
641 17 | 4
642 13 | 2
643 |
644 Y=5 | 1
645 |
646 +-----------------------------------
647 X=4 15 24 35 40 56 63
648 The points are in a wedge sqrt(2)*Y < X < Y. X is the bigger leg and
650 X^2 > Y^2/2 so X > Y*1/sqrt(2).
651 UAD Coordinates AB, AC, PQ -- Turn Right
653 In the UAD tree with coordinates AB, AC or PQ the path always turns to
654 the right. For example in AB coordinates at N=2 the path turns to the
655 right to go towards N=3.
656 coordinates => "AB"
658 20 | 3 N X,Y
660 | -- ------
661 12 | 2 1 3,4
662 | 2 5,12
663 | 3 21,20
664 4 | 1
665 | turn towards the
666 +------------------------- right at N=2
667 3 5 21
668 This can be proved from the transformations applied to seven cases, a
670 triplet U,A,D, then four crossing a gap within a level, then two
671 wrapping around at the end of a level. The initial N=1,2,3 can be
672 treated as a wrap-around from the end of depth=0 (the last case D to
673 U,A).
674 U triplet U,A,D
676 A
677 D
678 U.D^k.A crossing A,D to U
680 U.D^k.D across U->A gap
681 A.U^k.U k>=0
682 A.D^k.A crossing A,D to U
684 A.D^k.D across A->D gap
685 D.U^k.U k>=0
686 U.D^k.D crossing D to U,A
688 U.U^k.U across U->A gap
689 A.U^k.A k>=0
690 A.D^k.D crossing D to U,A
692 A.U^k.U across A->D gap
693 D.U^k.A k>=0
694 D^k .A wraparound A,D to U
696 D^k .D k>=0
697 U^(k+1).U
698 D^k wraparound D to U,A
700 U^k.U k>=0
701 U^k.A (k=0 is initial N=1,N=2,N=3 for none,U,A)
702 The powers U^k and D^k are an arbitrary number of descents U or D. In
704 P,Q coordinates, these powers are
705 U^k P,Q -> (k+1)*P-k*Q, k*P-(k-1)*Q
707 D^k P,Q -> P+2k*Q, Q
708 For AC coordinates, squaring to stretch to P^2,Q^2 doesn't change the
710 turns. Then a rotate by -45 degrees to A=P^2-Q^2, C=P^2+Q^2 also
711 doesn't change the turns.
712 UAD Coordinates BC -- Turn Left
714 In the UAD tree with coordinates BC the path always turns to the left.
715 For example in BC coordinates at N=2 the path turns to the right to go
716 towards N=3.
717 coordinates => "BC"
719 29 | 3 N X,Y
721 | -- ------
722 | 1 4,5
723 | 2 12,13
724 13 | 2 3 20,29
725 |
726 5 | 1 turn towards the
727 | left at N=2
728 +---------------
729 4 12 20
730 As per above, A,C turns to the right, which squared is A^2,C^2 to the
732 right too, which equals C^2-B^2,C^2. Negating the X coordinate to
733 B^2-C^2,C^2 mirrors to be a left turn always, and addition shearing to
734 X+Y,Y doesn't change that, giving B^2,C^2 always left and so B,C always
735 left.
736
738 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
739 classes.
740 "$path = Math::PlanePath::PythagoreanTree->new ()"
742 "$path = Math::PlanePath::PythagoreanTree->new (tree_type => $str,
743 coordinates => $str)"
744 Create and return a new path object. The "tree_type" option can be
745 "UAD" (the default)
747 "UArD" UAD with Gray code reflections
748 "FB"
749 "UMT"
750 The "coordinates" option can be
752 "AB" odd, even legs (the default)
754 "AC" odd leg, hypotenuse
755 "BC" even leg, hypotenuse
756 "PQ"
757 "SM" small, medium legs
758 "SC" small leg, hypotenuse
759 "MC" medium leg, hypotenuse
760 The "digit_order" option can be
762 "HtoL" high to low (the default)
764 "LtoH" low to high (the default)
765 "$n = $path->n_start()"
767 Return 1, the first N in the path.
768 "($x,$y) = $path->n_to_xy ($n)"
770 Return the X,Y coordinates of point number $n on the path. Points
771 begin at 1 and if "$n<1" then the return is an empty list.
772 "$n = $path->xy_to_n ($x,$y)"
774 Return the point number for coordinates "$x,$y". If there's
775 nothing at "$x,$y" then return "undef".
776 The return is "undef" if "$x,$y" is not a primitive Pythagorean
778 triple, per the "coordinates" option.
779 "$rsquared = $path->n_to_radius ($n)"
781 Return the radial distance R=sqrt(X^2+Y^2) of point $n. If there's
782 no point $n then return "undef".
783 For coordinates=AB or SM, this is the hypotenuse C and therefore an
785 integer, for integer $n.
786 "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
788 Return a range of N values which occur in a rectangle with corners
789 at $x1,$y1 and $x2,$y2. The range is inclusive.
790 Both trees go off into large X,Y coordinates while yet to finish
792 values close to the origin which means the N range for a rectangle
793 can be quite large. For UAD, $n_hi is roughly "3^max(x/2)", or for
794 FB smaller at roughly "3^log2(x)".
795 Descriptive Methods
797 "$x = $path->x_minimum()"
798 "$y = $path->y_minimum()"
799 Return the minimum X or Y occurring in the path. The value goes
800 according to the "coordinates" option,
801 coordinate minimum
803 ---------- -------
804 A,S 3
805 B,M 4
806 C 5
807 P 2
808 Q 1
809 Tree Methods
811 Each point has 3 children, so the path is a complete ternary tree.
812 "@n_children = $path->tree_n_children($n)"
814 Return the three children of $n, or an empty list if "$n < 1" (ie.
815 before the start of the path).
816 This is simply "3*$n-1, 3*$n, 3*$n+1". This is appending an extra
818 ternary digit 0, 1 or 2 to the mixed-radix form for N described
819 above. Or staying all in ternary then appending to N+1 rather than
820 N and adjusting back.
821 "$num = $path->tree_n_num_children($n)"
823 Return 3, since every node has three children, or return "undef" if
824 "$n<1" (ie. before the start of the path).
825 "$n_parent = $path->tree_n_parent($n)"
827 Return the parent node of $n, or "undef" if "$n <= 1" (the top of
828 the tree).
829 This is simply "floor(($n+1)/3)", reversing the "tree_n_children()"
831 calculation above.
832 "$depth = $path->tree_n_to_depth($n)"
834 Return the depth of node $n, or "undef" if there's no point $n.
835 The top of the tree at N=1 is depth=0, then its children depth=1,
836 etc.
837 The structure of the tree with 3 nodes per point means the depth is
839 floor(log3(2N-1)), so for example N=5 through N=13 all have
840 depth=2.
841 "$n = $path->tree_depth_to_n($depth)"
843 "$n = $path->tree_depth_to_n_end($depth)"
844 Return the first or last N at tree level $depth in the path, or
845 "undef" if nothing at that depth or not a tree. The top of the
846 tree is depth=0.
847 Tree Descriptive Methods
849 "$num = $path->tree_num_children_minimum()"
850 "$num = $path->tree_num_children_maximum()"
851 Return 3 since every node has 3 children, making that both the
852 minimum and maximum.
853 "$bool = $path->tree_any_leaf()"
855 Return false, since there are no leaf nodes in the tree.
856
858 UAD Matrices
859 Internally the code uses P,Q and calculates A,B at the end as
860 necessary. The UAD transformations in P,Q coordinates are
861 U P -> 2P-Q ( 2 -1 )
863 Q -> P ( 1 0 )
864 A P -> 2P+Q ( 2 1 )
866 Q -> P ( 1 0 )
867 D P -> P+2Q ( 1 2 )
869 Q -> Q unchanged ( 0 1 )
870 The advantage of P,Q for the calculation is that it's 2 values instead
872 of 3. The transformations can be written with the 2x2 matrices shown,
873 but explicit steps are enough for the code.
874 Repeatedly applying "U" gives
876 U 2P-Q, P
878 U^2 3P-2Q, 2P-Q
879 U^3 4P-3Q, 3P-2Q
880 ...
881 U^k (k+1)P-kQ, kP-(k-1)Q
882 = P+k(P-Q), Q+k*(P-Q)
883 If there's a run of k many high zeros in the Nrem = N-Nrow position in
885 the level then they can be applied to the initial P=2,Q=1 as
886 U^k P=k+2, Q=k+1 start for k high zeros
888 FB Transformations
890 The FB tree is calculated in P,Q and converted to A,B at the end as
891 necessary. Its three transformations are
892 M1 P -> P+Q ( 1 1 )
894 Q -> 2Q ( 0 2 )
895 M2 P -> 2P ( 2 0 )
897 Q -> P-Q ( 1 -1 )
898 M3 P -> 2P ( 2 0 )
900 Q -> P+Q ( 1 1 )
901 Price's paper shows rearrangements of a set of four values q',q,p,p'.
903 Just the p and q are enough for the calculation. The set of four has
904 some attractive geometric interpretations though.
905 X,Y to N -- UAD
907 "xy_to_n()" works in P,Q coordinates. An A,B or other input is
908 converted to P,Q per the formulas in "PQ Coordinates" above. P,Q can
909 be reversed up the UAD tree to its parent point
910 if P > 3Q reverse "D" P -> P-2Q
912 digit=2 Q -> unchanged
913 if P > 2Q reverse "A" P -> Q
915 digit=1 Q -> P-2Q
916 otherwise reverse "U" P -> Q
918 digit=0 Q -> 2Q-P
919 This gives a ternary digit 2, 1, 0 respectively from low to high.
921 Those plus a high "1" bit make N. The number of steps is the "depth"
922 level.
923 If at any stage P,Q doesn't satisfy P>Q>=1, one odd, the other even,
925 then it means the original point, however it was converted, was not a
926 primitive triple. For a primitive triple the endpoint is always
927 P=2,Q=1.
928 The conditions P>3Q or P>2Q work because each matrix sends its parent
930 P,Q to one of three disjoint regions,
931 Q P=Q P=2Q P=3Q
933 | * U ---- A ++++++
934 | * ---- ++++++
935 | * ---- ++++++
936 | * ---- ++++++
937 | * ---- ++++++
938 | * ---- ++++++
939 | * ---- ++++++ D
940 | * ----++++++
941 | * ----++++
942 | ----++
943 |
944 +------------------------------------------------- P
945 So U is the upper wedge, A the middle, and D the lower. The parent P,Q
947 can be anywhere in P>Q>=1, the matrices always map to these regions.
948 X,Y to N -- FB
950 After converting to P,Q as necessary, a P,Q point can be reversed up
951 the FB tree to its parent
952 if P odd reverse M1 P -> P-Q
954 (Q even) Q -> Q/2
955 if P > 2Q reverse M2 P -> P/2
957 (P even) Q -> P/2 - Q
958 otherwise reverse M3 P -> P/2
960 (P even) Q -> Q - P/2
961 This is a little like the binary greatest common divisor algorithm, but
963 designed for one value odd and the other even. Like the UAD ascent
964 above, if at any stage P,Q doesn't satisfy P>Q>=1, one odd, the other
965 even, then the initial point wasn't a primitive triple.
966 The M1 reversal works because M1 sends any parent P,Q to a child which
968 has P odd. All odd P,Q come from M1. The M2 and M3 always make
969 children with P even. Those children are divided between two disjoint
970 regions above and below the line P=2Q.
971 Q P=Q P=2Q
973 | * M3 P=even ----
974 | * ----
975 | * ----
976 | * ----
977 | * ---- M2 P=even
978 | * ----
979 | * ----
980 | * ----
981 | * ---- M1 P=odd anywhere
982 | ----
983 |
984 +------------------------------------------------- P
985 X,Y to N -- UMT
987 After converting to P,Q as necessary, a P,Q point can be reversed up
988 the UMT tree to its parent
989 if P > 2Q reverse "U" P -> Q
991 digit=0 Q -> 2Q-P
992 if P even reverse "M2" P -> P/2
994 (Q odd) Q -> P/2 - Q
995 otherwise reverse "T" P -> P - 3 * Q/2
997 (Q even) Q -> Q/2
998 These reversals work because U sends any parent P,Q to a child P>2Q
1000 whereas the M2 and T go below that line. M2 and T are distinguished by
1001 M2 giving P even whereas T gives P odd.
1002 Q P=Q P=2Q
1004 | * U ----
1005 | * ----
1006 | * ----
1007 | * ----
1008 | * ---- M2 for P=even
1009 | * ---- T for P=odd
1010 | * ----
1011 | * ----
1012 | * ----
1013 | ----
1014 |
1015 +------------------------------------------------- P
1016 Rectangle to N Range -- UAD
1018 For the UAD tree, the smallest A,B within each level is found at the
1019 topmost "U" steps for the smallest A or the bottom-most "D" steps for
1020 the smallest B. For example in the table above of level=2 N=5..13 the
1021 smallest A is the top A=7,B=24, and the smallest B is in the bottom
1022 A=35,B=12. In general
1023 Amin = 2*level + 1
1025 Bmin = 4*level
1026 In P,Q coordinates the same topmost line is the smallest P and bottom-
1028 most the smallest Q. The values are
1029 Pmin = level+1
1031 Qmin = 1
1032 The fixed Q=1 arises from the way the "D" transformation sends Q->Q
1034 unchanged, so every level includes a Q=1. This means if you ask what
1035 range of N is needed to cover all Q < someQ then there isn't one, only
1036 a P < someP has an N to go up to.
1037 Rectangle to N Range -- FB
1039 For the FB tree, the smallest A,B within each level is found in the
1040 topmost two final positions. For example in the table above of level=2
1041 N=5..13 the smallest A is in the top A=9,B=40, and the smallest B is in
1042 the next row A=35,B=12. In general,
1043 Amin = 2^level + 1
1045 Bmin = 2^level + 4
1046 In P,Q coordinates a Q=1 is found in that second row which is the
1048 minimum B, and the smallest P is found by taking M1 steps half-way then
1049 a M2 step, then M1 steps for the balance. This is a slightly
1050 complicated
1051 Pmin = / 3*2^(k-1) + 1 if even level = 2*k
1053 \ 2^(k+1) + 1 if odd level = 2*k+1
1054 Q = 1
1055 The fixed Q=1 arises from the M1 steps giving
1057 P = 2 + 1+2+4+8+...+2^(level-2)
1059 = 2 + 2^(level-1) - 1
1060 = 2^(level-1) + 1
1061 Q = 2^(level-1)
1062 followed by M2 step
1064 Q -> P-Q
1065 = 1
1066 As for the UAD above this means small Q's always remain no matter how
1068 big N gets, only a P range determines an N range.
1069
1071 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
1072 this path include,
1073 <http://oeis.org/A007051> (etc)
1075 A007051 N start of depth=n, (3^n+1)/2, ie. tree_depth_to_n()
1077 A003462 N end of depth=n-1, (3^n-1)/2, ie. tree_depth_to_n_end()
1078 A000244 N of row middle line, 3^n
1079 A058529 possible values taken by abs(A-B),
1081 being integers with all prime factors == +/-1 mod 8
1082 UAD Tree HtoL
1084 A321768 leg A
1085 A321769 leg B
1086 A321770 hypot C
1087 A321782 P (and the same for LtoH)
1088 A321783 Q
1089 A321784 P+Q
1090 A321785 P-Q
1091 UAD Tree
1093 A001542 row total p (even Pells)
1094 A001653 row total q (odd Pells)
1095 A001541 row total p + total q
1096 A002315 row total p - total q
1097 "U" repeatedly
1099 A046092 leg B, 2n(n+1) = 4*triangular numbers
1100 A099776 \ hypot C, being 2n(n+1)+1
1101 A001844 / which is the "centred squares"
1102 "A" repeatedly
1104 A046727 \ leg A
1105 A084159 / "Pell oblongs"
1106 A046729 leg B
1107 A001653 hypot C, numbers n where 2*n^2-1 is square
1108 A000129 P and Q, the Pell numbers
1109 A001652 leg S, the smaller
1110 A046090 leg M, the bigger
1111 "D" repeatedly
1113 A000466 leg A, being 4*n^2-1 for n>=1
1114 "M1" repeatedly
1116 A028403 leg B, binary 10..010..000
1117 A007582 leg B/4, binary 10..010..0
1118 A085601 hypot C, binary 10..010..001
1119 "M2" repeatedly
1121 A015249 \ leg A, binary 111000111000...
1122 A084152 |
1123 A084175 /
1124 A054881 leg B, binary 1010..1010000..00
1125 "M3" repeatedly
1127 A106624 P,Q pairs, 2^k-1,2^k
1128 "T" repeatedly
1130 A134057 leg A, binomial(2^n-1,2)
1131 binary 111..11101000..0001
1132 A093357 leg B, binary 10111..111000..000
1133 A052940 \
1134 A055010 | P, 3*2^n-1
1135 A083329 | binary 10111..111
1136 A153893 /
1137
1139 Math::PlanePath, Math::PlanePath::Hypot,
1140 Math::PlanePath::RationalsTree, Math::PlanePath::CoprimeColumns
1141
1143 <http://user42.tuxfamily.org/math-planepath/index.html>
1144
1146 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
1147 Kevin Ryde
1148 This file is part of Math-PlanePath.
1150 Math-PlanePath is free software; you can redistribute it and/or modify
1152 it under the terms of the GNU General Public License as published by
1153 the Free Software Foundation; either version 3, or (at your option) any
1154 later version.
1155 Math-PlanePath is distributed in the hope that it will be useful, but
1157 WITHOUT ANY WARRANTY; without even the implied warranty of
1158 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1159 General Public License for more details.
1160 You should have received a copy of the GNU General Public License along
1162 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
1163perl v5.32.1 2021-01-27Math::PlanePath::PythagoreanTree(3)