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, et al
21 "FB" Price
22 "UMT" a third form
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 all integers
36 <-A->
38 A primitive triple always has one of A,B odd and the other even. The
40 trees here have triples ordered as 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 depth=0 depth=1 depth=2 depth=3
95 N=1 N=2..4 N=5..13 N=14...
96 +-> 7,24 A,B coordinates
98 +-> 5,12 --+-> 55,48
99 | +-> 45,28
100 |
101 | +-> 39,80
102 3,4 --+-> 21,20 --+-> 119,120
103 | +-> 77,36
104 |
105 | +-> 33,56
106 +-> 15,8 --+-> 65,72
107 +-> 35,12
108 Counting N=1 as depth=0, each level has 3^depth many points and the
110 first N of a level ("tree_depth_to_n()") is at
111 Nrow = 1 + (1 + 3 + 3^2 + ... + 3^(depth-1))
113 = (3^depth + 1) / 2
114 The level numbering is like a mixed-radix representation of N where the
116 high digit is binary (so always 1) and the digits below are ternary.
117 +--------+---------+---------+-- --+---------+
119 N = | binary | ternary | ternary | ... | ternary |
120 +--------+---------+---------+-- --+---------+
121 1 0,1,2 0,1,2 0,1,2
122 The number of ternary digits is the "depth" and their value without the
124 high binary 1 is the position in the row.
125 A Repeatedly
127 Taking the middle "A" matrix repeatedly gives
128 3,4 -> 21,20 -> 119,120 -> 697,696 -> etc
130 which are the triples with legs A,B differing by 1 and therefore just
132 above or below the X=Y leading diagonal. The N values are 1,3,9,27,etc
133 = 3^depth.
134 D Repeatedly
136 Taking the lower "D" matrix repeatedly gives
137 3,4 -> 15,8 -> 35,12 -> 63,16 -> etc
139 which is the primitives among a sequence of triples known to the
141 ancients (Dickson's History of the Theory of Numbers, start of chapter
142 IV),
143 A = k^2-1 k even for primitives
145 B = 2*k
146 C = k^2+1 so C=A+2
147 When k is even these are primitive. If k is odd then A and B are both
149 even, ie. a common factor of 2, so not primitive. These points are the
150 last of each level, so at N=(3^(depth+1)-1)/2 which is
151 "tree_depth_to_n_end()".
152 U Repeatedly
154 Taking the upper "U" matrix repeatedly gives
155 3.4 -> 5,12 -> 7,24 -> 9,40 -> etc
157 with C=B+1 and A the odd numbers. These are the first of each level so
159 at Nrow described above. The resulting triples are a sequence known to
160 Pythagoras (Dickson's History of the Theory of Numbers, start of
161 chapter IV).
162 A = any odd integer, so A^2 any odd square
164 B = (A^2-1)/2
165 C = (A^2+1)/2
166 / A^2-1 \ / A^2+1 \
168 A^2 + | ------ |^2 = | ----- |^2
169 \ 2 / \ 2 /
170 This is also described by Fibonacci in his Liber Quadratorum (Book of
172 Squares) in terms of sums of odd numbers
173 s = any odd square = A^2
175 B^2 = 1 + 3 + 5 + ... + s-2 = ((s-1)/2)^2
176 C^2 = 1 + 3 + 5 + ... + s-2 + s = ((s+1)/2)^2
177 so C^2 = A^2 + B^2
178 eg. s=25=A^2 B^2=((25-1)/2)^2=144 so A=5,B=12
180 The geometric interpretation is that an existing square of side B is
182 extended by a "gnomon" around two sides making a new larger square of
183 side C=B+1. The length of the gnomon is odd and when it's an odd
184 square then the new total area is the sum of two squares.
185 *****gnomon******* gnomon length an odd square = A^2
187 +--------------+ *
188 | | * so new bigger square area
189 | square | * C^2 = A^2 + B^2
190 | with side B | *
191 | | *
192 +--------------+ *
193 See Math::PlanePath::Corner for a path following such gnomons.
195 UArD Tree
197 Option "tree_type => "UArD"" varies the UAD tree by applying a left-
198 right reflection under each "A" matrix. The result is ternary
199 reflected Gray code order. The 3 children under each node are
200 unchanged, just their order.
201 +-> 7,24 tree_type => "UArD"
203 +-> 5,12 --+-> 55,48 A,B coordinates
204 | +-> 45,28
205 |
206 | +-> 77,36 <-+- U,D legs swapped
207 3,4 --+-> 21,20 --+-> 119,120 |
208 | +-> 39,80 <-+
209 |
210 | +-> 33,56
211 +-> 15,8 --+-> 65,72
212 +-> 35,12
213 Notice the middle points 77,36 and 39,80 are swapped relative to the
215 UAD shown above. In general the whole tree underneath an "A" is
216 mirrored. If there's an even number of "A"s above then those
217 mirrorings cancel out to be plain again.
218 This tree form is primarily of interest for "Digit Order Low to High"
220 described below since it gives points in order clockwise down from the
221 Y axis.
222 In "PQ Coordinates" below, with the default digits high to low, UArD
224 also makes successive steps across the row either horizontal or
225 45-degrees NE-SW.
226 In all cases the Gray coding is applied to N first, then the resulting
228 digits are interpreted either high to low (the default) or low to high
229 ("LtoH" option).
230 FB Tree
232 Option "tree_type => "FB"" selects a tree independently by
233 V. E. Firstov, "A Special Matrix Transformation Semigroup of
235 Primitive Pairs and the Genealogy of Pythagorean Triples",
236 Matematicheskie Zametki, 2008, volume 84, number 2, pages 281-299
237 (in Russian), and Mathematical Notes, 2008, volume 84, number 2,
238 pages 263-279 (in English)
239 H. Lee Price, "The Pythagorean Tree: A New Species", 2008,
241 <http://arxiv.org/abs/0809.4324> (version 2)
242 Firstov finds this tree by semigroup transformations. Price finds it
244 by expressing triples in certain "Fibonacci boxes" with a box of four
245 values q',q,p,p' having p=q+q' and p'=p+q so each is the sum of the
246 preceding two in a fashion similar to the Fibonacci sequence. A box
247 where p and q have no common factor corresponds to a primitive triple.
248 See "PQ Coordinates" and "FB Transformations" below.
249 tree_type => "FB"
251 Y=40 | 5
253 |
254 |
255 |
256 | 17
257 Y=24 | 4
258 |
259 | 8
260 |
261 Y=12 | 2 6
262 |
263 | 3
264 Y=4 | 1
265 |
266 +----------------------------------------------
267 X=3 X=15 x=21 X=35
268 For a given box three transformations can be applied to go to new boxes
270 corresponding to new primitive triples. This visits all and only
271 primitive triples, but in a different order to the UAD above.
272 The first point N=1 is again at X=3,Y=4, from which three further
274 points N=2,3,4 are derived, then three more from each of those, etc.
275 N=1 N=2..4 N=5..13 N=14...
277 +-> 9,40 A,B coordinates
279 +-> 5,12 --+-> 35,12
280 | +-> 11,60
281 |
282 | +-> 21,20
283 3,4 --+-> 15,8 --+-> 55,48
284 | +-> 39,80
285 |
286 | +-> 13,84
287 +-> 7,24 --+-> 63,16
288 +-> 15,112
289 UMT Tree
291 Option "tree_type =" "UMT"> is a third tree type by Firstov (reference
292 above). It's a combination of "U", "M2" and a third matrix T = M1*D.
293 U +-> 7,24 A,B coordinates
295 +-> 5,12 --+-> 35,12
296 | +-> 65,72
297 |
298 | M2 +-> 33,56
299 3,4 --+-> 15,8 --+-> 55,48
300 | +-> 45,28
301 |
302 | T +-> 39,80
303 +-> 21,20 --+-> 91,60
304 +-> 105,88
305 The first "T" child 21,20 is the same as the "A" matrix, but it differs
307 at further levels down. For example "T" twice is 105,88 which is not
308 the same as "A" twice 119,120.
309 Digit Order Low to High
311 Option "digit_order => 'LtoH'" applies matrices using the ternary
312 digits of N taken from low to high. The points in each row are
313 unchanged, as is the parent-child N numbering, but the X,Y values are
314 rearranged within the row.
315 The UAD matrices send points to disjoint regions and the effect of LtoH
317 is to keep the tree growing into those separate wedge regions. The
318 arms grow roughly as follows
319 tree_type => "UAD", digit_order => "LtoH"
321 Y=80 | 6 UAD LtoH
323 | /
324 | /
325 Y=56 | / 7 10 9
326 | / / / /
327 | / / | / 8
328 | / _/ / / /
329 | / / / / /
330 Y=24 | 5 / / | / _/ __--11
331 | / / _/ |/_/ __--
332 Y=20 | / / / __3 __-- _____----12
333 | |/_/ __-- __--- ____-----
334 Y=12 | 2 __-- _/___---- ____13
335 | / __-- __-- _____-----
336 | /_--_____---4-----
337 Y=4 | 1---
338 |
339 +--------------------------------------------------
340 X=3 X=15 X=20 X=35 X=76
341 Notice the points of the second row N=5 to N=13 are almost clockwise
343 down from the Y axis, except N=8,9,10 go upwards. Those N=8,9,10 go
344 upwards because the A matrix has a reflection (its determinant is -1).
345 Option "tree_type => "UArD"" reverses the tree underneath each A, and
347 that plus LtoH gives A,B points going clockwise in each row. P,Q
348 coordinates go clockwise too.
349 AC Coordinates
351 Option "coordinates => 'AC'" gives the A and C legs of each triple as
352 X=A,Y=C.
353 coordinates => "AC"
355 85 | 122 10
357 |
358 |
359 73 | 6
360 |
361 65 | 11 40
362 61 | 41
363 |
364 | 7
365 |
366 |
367 41 | 14
368 | 13
369 35 |
370 | 3
371 25 | 5
372 |
373 17 | 4
374 13 | 2
375 |
376 Y=5 | 1
377 |
378 +-------------------------------------------
379 X=3 7 9 21 35 45 55 63 77
380 Since A<C the coordinates are X<Y all above the X=Y diagonal. The "D
382 Repeatedly" triples described above have C=A+2 so they are the points
383 Y=X+2 just above the diagonal.
384 For the FB tree the set of points visited is the same, but with a
386 different N numbering.
387 tree_type => "FB", coordinates => "AC"
389 85 | 11 35
391 |
392 |
393 73 | 9
394 |
395 65 | 23 12
396 61 | 7
397 |
398 | 17
399 |
400 |
401 41 | 5
402 | 6
403 35 |
404 | 8
405 25 | 4
406 |
407 17 | 3
408 13 | 2
409 |
410 Y=5 | 1
411 |
412 +-------------------------------------------
413 X=3 7 9 21 35 45 55 63 77
414 BC Coordinates
416 Option "coordinates => 'BC'" gives the B and C legs of each triple as
417 X=B,Y=C. This is the B=even and C=long legs of all primitive triples.
418 This combination has points on 45-degree straight lines.
419 coordinates => "BC"
421 101 | 121
423 97 | 12
424 |
425 89 | 8
426 85 | 10 122
427 |
428 |
429 73 | 6
430 |
431 65 | 40 11
432 61 | 41
433 |
434 | 7
435 |
436 |
437 41 | 14
438 | 13
439 35 |
440 | 3
441 25 | 5
442 |
443 17 | 4
444 13 | 2
445 |
446 Y=5 | 1
447 |
448 +--------------------------------------------------
449 X=4 12 24 40 60 84
450 Since B<C the coordinates are X<Y above the X=Y leading diagonal.
452 N=1,2,5,14,41,etc along the X=Y-1 diagonal are the "U Repeatedly"
453 triples described above which have C=B+1 and are at the start of each
454 tree row.
455 For the FB tree the set of points visited is the same, but with a
457 different N numbering.
458 tree_type => "FB", coordinates => "BC"
460 101 | 15
462 97 | 50
463 |
464 89 | 10
465 85 | 35 11
466 |
467 |
468 73 | 9
469 |
470 65 | 12 23
471 61 | 7
472 |
473 | 17
474 |
475 |
476 41 | 5
477 | 6
478 35 |
479 | 8
480 25 | 4
481 |
482 17 | 3
483 13 | 2
484 |
485 Y=5 | 1
486 |
487 +----------------------------------------------
488 X=4 12 24 40 60 84
489 As seen from the diagrams, the B,C points fall on 45-degree straight
491 lines going up from X=Y-1. This occurs because a primitive triple
492 A,B,C with A odd and B even can be written
493 A^2 = C^2 - B^2
495 = (C+B)*(C-B)
496 gcd(A,B)=1 means also gcd(C+B,C-B)=1 and so since C+B and C-B have no
498 common factor they must each be squares to give A^2. Call them s^2 and
499 t^2,
500 C+B = s^2 and conversely C = (s^2 + t^2)/2
502 C-B = t^2 B = (s^2 - t^2)/2
503 s = odd integer s >= 3
505 t = odd integer s > t >= 1
506 with gcd(s,t)=1 so that gcd(C+B,C-B)=1
507 When t=1 this is C=(s^2+1)/2 and B=(s^2-1)/2 which is the "U"-repeated
509 points at Y=X+1 for each s. As t increases the B,C coordinate
510 combination makes a line upwards at 45-degrees from those t=1
511 positions,
512 C + B = s^2 anti-diagonal 45-degrees,
514 position along diagonal determined by t
515 All primitive triples start from a C=B+1 with C=(s^2+1)/2 half an odd
517 square, and go up from there. To ensure the triple is primitive must
518 have gcd(s,t)=1. Values of t where gcd(s,t)!=1 are gaps in the anti-
519 diagonal lines.
520 PQ Coordinates
522 Primitive Pythagorean triples can be parameterized as follows for A odd
523 and B even. This is per Diophantus, and anonymous Arabic manuscript
524 for constraining it to primitive triples (Dickson's History of the
525 Theory of Numbers).
526 A = P^2 - Q^2
528 B = 2*P*Q
529 C = P^2 + Q^2
530 with P > Q >= 1, one odd, one even, and no common factor
531 P = sqrt((C+A)/2)
533 Q = sqrt((C-A)/2)
534 The first P=2,Q=1 is the triple A=3,B=4,C=5.
536 Option "coordinates => 'PQ'" gives these as X=P,Y=Q, for either
538 "tree_type". Because P>Q>=1 the values fall in the eighth of the plane
539 below the X=Y diagonal,
540 tree_type => "UAD", coordinates => "PQ"
542 10 | 9842
544 9 | 3281
545 8 | 1094 23
546 7 | 365 32
547 6 | 122 38
548 5 | 41 8
549 4 | 14 11 12 15
550 3 | 5 6 16
551 2 | 2 3 7 10 22
552 1 | 1 4 13 40 121
553 Y=0 |
554 +--------------------------------------------------------
555 X=0 1 2 3 4 5 6 7 8 9 10 11
556 The diagonal N=1,2,5,14,41,etc is P=Q+1 as per "U Repeatedly" above.
558 The one-to-one correspondence between P,Q and A,B means both tree types
560 visit all P,Q pairs, so all X,Y with no common factor and one odd one
561 even. There's other ways to iterate through such coprime pairs and any
562 such method would generate Pythagorean triples too, in a different
563 order from the trees here.
564 The letters P and Q here are a little bit arbitrary. This
566 parameterization is often written m,n or u,v but don't want "n" to be
567 confused that with N point numbering or "u" to be confused with the U
568 matrix.
569 SM Coordinates
571 Option "coordinates => 'SM'" gives the small and medium legs from each
572 triple as X=small,Y=medium. This is like "AB" except that if A>B then
573 they're swapped to X=B,Y=A so X<Y always. The effect is to mirror the
574 AB points below the X=Y diagonal up to the upper eighth,
575 coordinates => "SM"
577 91 | 16
579 84 | 122
580 | 8
581 | 10
582 72 | 12
583 |
584 |
585 60 | 41 40
586 | 11
587 55 | 6
588 |
589 | 7
590 40 | 14
591 |
592 35 | 13
593 |
594 24 | 5
595 21 | 3
596 |
597 12 | 2 4
598 |
599 Y=4 | 1
600 |
601 +----------------------------------------
602 X=3 8 20 33 48 60 65
603 SC Coordinates
605 Option "coordinates => 'SC'" gives the small leg and hypotenuse from
606 each triple,
607 coordinates => "SC"
609 85 | 122 10
611 |
612 |
613 73 | 6
614 |
615 | 40 11
616 61 | 41
617 |
618 53 | 7
619 |
620 |
621 41 | 14
622 37 | 13
623 |
624 | 3
625 25 | 5
626 |
627 | 4
628 13 | 2
629 |
630 Y=5 | 1
631 |
632 +-----------------------------
633 X=3 8 20 33 48
634 The points are all X < 0.7*Y since with X as the smaller leg must have
636 X^2 < Y^2/2 so X < Y*1/sqrt(2).
637 MC Coordinates
639 Option "coordinates => 'MC'" gives the medium leg and hypotenuse from
640 each triple,
641 coordinates => "MC"
643 65 | 11 40
645 61 | 41
646 |
647 53 | 7
648 |
649 |
650 41 | 14
651 37 | 13
652 |
653 29 | 3
654 25 | 5
655 |
656 17 | 4
657 13 | 2
658 |
659 Y=5 | 1
660 |
661 +-----------------------------------
662 X=4 15 24 35 40 56 63
663 The points are in a wedge 0.7*Y < X < Y. X is the bigger leg and
665 X^2 > Y^2/2 so X > Y*1/sqrt(2).
666 UAD Coordinates AB, AC, PQ -- Turn Right
668 In the UAD tree with coordinates AB, AC or PQ the path always turns to
669 the right. For example in AB coordinates at N=2 the path turns to the
670 right to go towards N=3.
671 coordinates => "AB"
673 20 | 3 N X,Y
675 | -- ------
676 12 | 2 1 3,4
677 | 2 5,12
678 | 3 21,20
679 4 | 1
680 | turn towards the
681 +------------------------- right at N=2
682 3 5 21
683 This can be proved from the transformations applied to seven cases, a
685 triplet U,A,D, then four crossing a gap within a level, then two
686 wrapping around at the end of a level. The initial N=1,2,3 can be
687 treated as a wrap-around from the end of depth=0 (the last case D to
688 U,A).
689 U triplet U,A,D
691 A
692 D
693 U.D^k.A crossing A,D to U
695 U.D^k.D across U->A gap
696 A.U^k.U k>=0
697 A.D^k.A crossing A,D to U
699 A.D^k.D across A->D gap
700 D.U^k.U k>=0
701 U.D^k.D crossing D to U,A
703 U.U^k.U across U->A gap
704 A.U^k.A k>=0
705 A.D^k.D crossing D to U,A
707 A.U^k.U across A->D gap
708 D.U^k.A k>=0
709 D^k .A wraparound A,D to U
711 D^k .D k>=0
712 U^(k+1).U
713 D^k wraparound D to U,A
715 U^k.U k>=0
716 U^k.A (k=0 is initial N=1,N=2,N=3 for none,U,A)
717 The powers U^k and D^k are an arbitrary number of descents U or D. In
719 P,Q coordinates these powers are
720 U^k P,Q -> (k+1)*P-k*Q, k*P-(k-1)*Q
722 D^k P,Q -> P+2k*Q, Q
723 For AC coordinates squaring to stretch to P^2,Q^2 doesn't change the
725 turns. Then a rotate by -45 degrees to A=P^2-Q^2, C=P^2+Q^2 also
726 doesn't change the turns.
727 UAD Coordinates BC -- Turn Left
729 In the UAD tree with coordinates BC the path always turns to the left.
730 For example in BC coordinates at N=2 the path turns to the right to go
731 towards N=3.
732 coordinates => "BC"
734 29 | 3 N X,Y
736 | -- ------
737 | 1 4,5
738 | 2 12,13
739 13 | 2 3 20,29
740 |
741 5 | 1 turn towards the
742 | left at N=2
743 +---------------
744 4 12 20
745 As per above A,C turns to the right, which squared is A^2,C^2 to the
747 right too, which equals C^2-B^2,C^2. Negating the X coordinate to
748 B^2-C^2,C^2 mirrors to be a left turn always, and addition shearing to
749 X+Y,Y doesn't change that, giving B^2,C^2 always left and so B,C always
750 left.
751
753 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
754 classes.
755 "$path = Math::PlanePath::PythagoreanTree->new ()"
757 "$path = Math::PlanePath::PythagoreanTree->new (tree_type => $str,
758 coordinates => $str)"
759 Create and return a new path object. The "tree_type" option can be
760 "UAD" (the default)
762 "UArD" UAD with Gray code reflections
763 "FB"
764 "UMT"
765 The "coordinates" option can be
767 "AB" odd, even legs (the default)
769 "AC" odd leg, hypotenuse
770 "BC" even leg, hypotenuse
771 "PQ"
772 "SM" small, medium legs
773 "SC" small leg, hypotenuse
774 "MC" medium leg, hypotenuse
775 The "digit_order" option can be
777 "HtoL" high to low (the default)
779 "LtoH" low to high (the default)
780 "$n = $path->n_start()"
782 Return 1, the first N in the path.
783 "($x,$y) = $path->n_to_xy ($n)"
785 Return the X,Y coordinates of point number $n on the path. Points
786 begin at 1 and if "$n<1" then the return is an empty list.
787 "$n = $path->xy_to_n ($x,$y)"
789 Return the point number for coordinates "$x,$y". If there's
790 nothing at "$x,$y" then return "undef".
791 The return is "undef" if "$x,$y" is not a primitive Pythagorean
793 triple, per the "coordinates" option.
794 "$rsquared = $path->n_to_radius ($n)"
796 Return the radial distance R=sqrt(X^2+Y^2) of point $n. If there's
797 no point $n then return "undef".
798 For coordinates=AB or SM this is the hypotenuse C and therefore an
800 integer, for integer $n.
801 "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
803 Return a range of N values which occur in a rectangle with corners
804 at $x1,$y1 and $x2,$y2. The range is inclusive.
805 Both trees go off into large X,Y coordinates while yet to finish
807 values close to the origin which means the N range for a rectangle
808 can be quite large. For UAD $n_hi is roughly "3**max(x/2)", or for
809 FB smaller at roughly "3**log2(x)".
810 Descriptive Methods
812 "$x = $path->x_minimum()"
813 "$y = $path->y_minimum()"
814 Return the minimum X or Y occurring in the path. The value goes
815 according to the "coordinates" option,
816 coordinate minimum
818 ---------- -------
819 A,S 3
820 B,M 4
821 C 5
822 P 2
823 Q 1
824 Tree Methods
826 Each point has 3 children, so the path is a complete ternary tree.
827 "@n_children = $path->tree_n_children($n)"
829 Return the three children of $n, or an empty list if "$n < 1" (ie.
830 before the start of the path).
831 This is simply "3*$n-1, 3*$n, 3*$n+1". This is appending an extra
833 ternary digit 0, 1 or 2 to the mixed-radix form for N described
834 above. Or staying all in ternary then appending to N+1 rather than
835 N and adjusting back.
836 "$num = $path->tree_n_num_children($n)"
838 Return 3, since every node has three children, or return "undef" if
839 "$n<1" (ie. before the start of the path).
840 "$n_parent = $path->tree_n_parent($n)"
842 Return the parent node of $n, or "undef" if "$n <= 1" (the top of
843 the tree).
844 This is simply "floor(($n+1)/3)", reversing the "tree_n_children()"
846 calculation above.
847 "$depth = $path->tree_n_to_depth($n)"
849 Return the depth of node $n, or "undef" if there's no point $n.
850 The top of the tree at N=1 is depth=0, then its children depth=1,
851 etc.
852 The structure of the tree with 3 nodes per point means the depth is
854 floor(log3(2N-1)), so for example N=5 through N=13 all have
855 depth=2.
856 "$n = $path->tree_depth_to_n($depth)"
858 "$n = $path->tree_depth_to_n_end($depth)"
859 Return the first or last N at tree level $depth in the path, or
860 "undef" if nothing at that depth or not a tree. The top of the
861 tree is depth=0.
862 Tree Descriptive Methods
864 "$num = $path->tree_num_children_minimum()"
865 "$num = $path->tree_num_children_maximum()"
866 Return 3 since every node has 3 children, making that both the
867 minimum and maximum.
868 "$bool = $path->tree_any_leaf()"
870 Return false, since there are no leaf nodes in the tree.
871
873 UAD Matrices
874 Internally the code uses P,Q and calculates A,B at the end as
875 necessary. The UAD transformations in P,Q coordinates are
876 U P -> 2P-Q ( 2 -1 )
878 Q -> P ( 1 0 )
879 A P -> 2P+Q ( 2 1 )
881 Q -> P ( 1 0 )
882 D P -> P+2Q ( 1 2 )
884 Q -> Q unchanged ( 0 1 )
885 The advantage of P,Q for the calculation is that it's 2 values instead
887 of 3. The transformations can be written with the 2x2 matrices shown,
888 but explicit steps are enough for the code.
889 Repeatedly applying "U" gives
891 U 2P-Q, P
893 U^2 3P-2Q, 2P-Q
894 U^3 4P-3Q, 3P-2Q
895 ...
896 U^k (k+1)P-kQ, kP-(k-1)Q
897 = P+k(P-Q), Q+k*(P-Q)
898 If there's a run of k many high zeros in the Nrem = N-Nrow position in
900 the level then they can be applied to the initial P=2,Q=1 as
901 U^k P=k+2, Q=k+1 start for k high zeros
903 FB Transformations
905 The FB tree is calculated in P,Q and converted to A,B at the end as
906 necessary. Its three transformations are
907 M1 P -> P+Q ( 1 1 )
909 Q -> 2Q ( 0 2 )
910 M2 P -> 2P ( 2 0 )
912 Q -> P-Q ( 1 -1 )
913 M3 P -> 2P ( 2 0 )
915 Q -> P+Q ( 1 1 )
916 Price's paper shows rearrangements of a set of four values q',q,p,p'.
918 Just the p and q are enough for the calculation. The set of four has
919 some attractive geometric interpretations though.
920 X,Y to N -- UAD
922 "xy_to_n()" works in P,Q coordinates. An A,B or other input is
923 converted to P,Q per the formulas in "PQ Coordinates" above. A P,Q
924 point can be reversed up the UAD tree to its parent point
925 if P > 3Q reverse "D" P -> P-2Q
927 digit=2 Q -> unchanged
928 if P > 2Q reverse "A" P -> Q
930 digit=1 Q -> P-2Q
931 otherwise reverse "U" P -> Q
933 digit=0 Q -> 2Q-P
934 This gives a ternary digit 2, 1, 0 respectively from low to high.
936 Those plus a high "1" bit make N. The number of steps is the "depth"
937 level.
938 If at any stage P,Q doesn't satisfy P>Q>=1, one odd, the other even,
940 then it means the original point, however it was converted, was not a
941 primitive triple. For a primitive triple the endpoint is always
942 P=2,Q=1.
943 The conditions P>3Q or P>2Q work because each matrix sends its parent
945 P,Q to one of three disjoint regions,
946 Q P=Q P=2Q P=3Q
948 | * U ---- A ++++++
949 | * ---- ++++++
950 | * ---- ++++++
951 | * ---- ++++++
952 | * ---- ++++++
953 | * ---- ++++++
954 | * ---- ++++++ D
955 | * ----++++++
956 | * ----++++
957 | ----++
958 |
959 +------------------------------------------------- P
960 So U is the upper wedge, A the middle, and D the lower. The parent P,Q
962 can be anywhere in P>Q>=1, the matrices always map to these regions.
963 X,Y to N -- FB
965 After converting to P,Q as necessary, a P,Q point can be reversed up
966 the FB tree to its parent
967 if P odd reverse M1 P -> P-Q
969 (Q even) Q -> Q/2
970 if P > 2Q reverse M2 P -> P/2
972 (P even) Q -> P/2 - Q
973 otherwise reverse M3 P -> P/2
975 (P even) Q -> Q - P/2
976 This is a little like the binary greatest common divisor algorithm, but
978 designed for one value odd and the other even. Like the UAD ascent
979 above if at any stage P,Q doesn't satisfy P>Q>=1, one odd, the other
980 even, then the initial point wasn't a primitive triple.
981 The M1 reversal works because M1 sends any parent P,Q to a child which
983 has P odd. All odd P,Q comes from M1. The M2 and M3 always make
984 children with P even. Those children are divided between two disjoint
985 regions above and below the line P=2Q.
986 Q P=Q P=2Q
988 | * M3 P=even ----
989 | * ----
990 | * ----
991 | * ----
992 | * ---- M2 P=even
993 | * ----
994 | * ----
995 | * ----
996 | * ---- M1 P=odd anywhere
997 | ----
998 |
999 +------------------------------------------------- P
1000 X,Y to N -- UMT
1002 After converting to P,Q as necessary, a P,Q point can be reversed up
1003 the UMT tree to its parent
1004 if P > 2Q reverse "U" P -> Q
1006 digit=0 Q -> 2Q-P
1007 if P even reverse "M2" P -> P/2
1009 (Q odd) Q -> P/2 - Q
1010 otherwise reverse "T" P -> P - 3 * Q/2
1012 (Q even) Q -> Q/2
1013 These reversals work because U sends any parent P,Q to a child P>2Q
1015 whereas the M2 and T go below that line. M2 and T are distinguished by
1016 M2 giving P even whereas T gives P odd.
1017 Q P=Q P=2Q
1019 | * U ----
1020 | * ----
1021 | * ----
1022 | * ----
1023 | * ---- M2 for P=even
1024 | * ---- T for P=odd
1025 | * ----
1026 | * ----
1027 | * ----
1028 | ----
1029 |
1030 +------------------------------------------------- P
1031 Rectangle to N Range -- UAD
1033 For the UAD tree, the smallest A,B within each level is found at the
1034 topmost "U" steps for the smallest A or the bottom-most "D" steps for
1035 the smallest B. For example in the table above of level=2 N=5..13 the
1036 smallest A is the top A=7,B=24, and the smallest B is in the bottom
1037 A=35,B=12. In general
1038 Amin = 2*level + 1
1040 Bmin = 4*level
1041 In P,Q coordinates the same topmost line is the smallest P and bottom-
1043 most the smallest Q. The values are
1044 Pmin = level+1
1046 Qmin = 1
1047 The fixed Q=1 arises from the way the "D" transformation sends Q->Q
1049 unchanged, so every level includes a Q=1. This means if you ask what
1050 range of N is needed to cover all Q < someQ then there isn't one, only
1051 a P < someP has an N to go up to.
1052 Rectangle to N Range -- FB
1054 For the FB tree, the smallest A,B within each level is found in the
1055 topmost two final positions. For example in the table above of level=2
1056 N=5..13 the smallest A is in the top A=9,B=40, and the smallest B is in
1057 the next row A=35,B=12. In general,
1058 Amin = 2^level + 1
1060 Bmin = 2^level + 4
1061 In P,Q coordinates a Q=1 is found in that second row which is the
1063 minimum B, and the smallest P is found by taking M1 steps half-way then
1064 a M2 step, then M1 steps for the balance. This is a slightly
1065 complicated
1066 Pmin = / 3*2^(k-1) + 1 if even level = 2*k
1068 \ 2^(k+1) + 1 if odd level = 2*k+1
1069 Q = 1
1070 The fixed Q=1 arises from the M1 steps giving
1072 P = 2 + 1+2+4+8+...+2^(level-2)
1074 = 2 + 2^(level-1) - 1
1075 = 2^(level-1) + 1
1076 Q = 2^(level-1)
1077 followed by M2 step
1079 Q -> P-Q
1080 = 1
1081 As for the UAD above this means small Q's always remain no matter how
1083 big N gets, only a P range determines an N range.
1084
1086 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
1087 this path include,
1088 <http://oeis.org/A007051> (etc)
1090 A007051 N start of depth=n, (3^n+1)/2, ie. tree_depth_to_n()
1092 A003462 N end of depth=n-1, (3^n-1)/2, ie. tree_depth_to_n_end()
1093 A000244 N of row middle line, 3^n
1094 A058529 possible values taken by abs(A-B),
1096 being integers with all prime factors == +/-1 mod 8
1097 A001542 UAD row total p (even Pells)
1099 A001653 UAD row total q (odd Pells)
1100 A001541 UAD row total p + total q
1101 A002315 UAD row total p - total q
1102 "U" repeatedly
1104 A046092 coordinate B, 2n(n+1) = 4*triangular numbers
1105 A099776 \ coordinate C, being 2n(n+1)+1
1106 A001844 / which is the "centred squares"
1107 "A" repeatedly
1109 A046727 \ coordinate A
1110 A084159 / "Pell oblongs"
1111 A046729 coordinate B
1112 A001653 coordinate C, numbers n where 2*n^2-1 is square
1113 A000129 coordinate P and Q, the Pell numbers
1114 A001652 coordinate S, the smaller leg
1115 A046090 coordinate M, the bigger leg
1116 "D" repeatedly
1118 A000466 coordinate A, being 4*n^2-1 for n>=1
1119 "M1" repeatedly
1121 A028403 coordinate B, binary 10..010..000
1122 A007582 coordinate B/4, binary 10..010..0
1123 A085601 coordinate C, binary 10..010..001
1124 "M2" repeatedly
1126 A015249 \ coordinate A, binary 111000111000...
1127 A084152 |
1128 A084175 /
1129 A054881 coordinate B, binary 1010..1010000..00
1130 "M3" repeatedly
1132 A106624 coordinate P,Q pairs, 2^k-1,2^k
1133 "T" repeatedly
1135 A134057 coordinate A, binomial(2^n-1,2)
1136 binary 111..11101000..0001
1137 A093357 coordinate B, binary 10111..111000..000
1138 A052940 \
1139 A055010 | coordinate P, 3*2^n-1
1140 A083329 | binary 10111..111
1141 A153893 /
1142
1144 Math::PlanePath, Math::PlanePath::Hypot,
1145 Math::PlanePath::RationalsTree, Math::PlanePath::CoprimeColumns
1146
1148 <http://user42.tuxfamily.org/math-planepath/index.html>
1149
1151 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017 Kevin Ryde
1152 This file is part of Math-PlanePath.
1154 Math-PlanePath is free software; you can redistribute it and/or modify
1156 it under the terms of the GNU General Public License as published by
1157 the Free Software Foundation; either version 3, or (at your option) any
1158 later version.
1159 Math-PlanePath is distributed in the hope that it will be useful, but
1161 WITHOUT ANY WARRANTY; without even the implied warranty of
1162 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1163 General Public License for more details.
1164 You should have received a copy of the GNU General Public License along
1166 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
1167perl v5.28.0 2017-12-03Math::PlanePath::PythagoreanTree(3)