1Math::PlanePath::PythagUosreeranCTorneter(i3b)uted PerlMDaotchu:m:ePnltaanteiPoanth::PythagoreanTree(3)
2
3
4
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
20 "UAD" Berggren, Barning, Hall, and others
21 "FB" Firstov and Price
22 "UMT" Firstov
23
24 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
28 A^2 + B^2 = C^2 gcd(A,B) = 1, no common factor
29 X=A, Y=B
30
31 ^ * ^
32 / /| | right triangle
33 C / | B A side odd
34 / / | | B side even
35 v *---* v C hypotenuse
36 (all integers)
37 <-A->
38
39 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
42 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
47 <http://user42.tuxfamily.org/triples/index.html>
48
49 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
55 tree_type => "UAD" (the default)
56
57 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
74 The UAD matrices are
75
76 / 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
80 They're multiplied on the right of an (A,B,C) column vector, for
81 example
82
83 / 3 \ / 5 \
84 U * | 4 | = | 12 |
85 \ 5 / \ 13 /
86
87 The starting point is N=1 at X=3,Y=4 which is the well-known triple
88
89 3^2 + 4^2 = 5^2
90
91 From it three further points N=2, N=3 and N=4 are derived, then three
92 more from each of those, etc,
93
94 tree_type => "UAD" coordinates A,B
95
96 ______________ 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
102 rows depth = 0 N=1
103 depth = 1 N=2..4
104 depth = 2 N=5..13
105 depth = 3 N=14..
106
107 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
110 Nrow = 1 + (1 + 3 + 3^2 + ... + 3^(depth-1))
111 = (3^depth + 1) / 2
112 = 1, 2, 5, 14, 41, 122, 365, ... (A007051)
113
114 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
117 +--------+---------+---------+-- --+---------+
118 N = | binary | ternary | ternary | ... | ternary |
119 +--------+---------+---------+-- --+---------+
120 1 0,1,2 0,1,2 0,1,2
121
122 The number of ternary digits is the "depth" and their value without the
123 high binary 1 is the position in the row.
124
125 U Repeatedly
126 Taking the upper "U" matrix repeatedly gives
127
128 3.4 -> 5,12 -> 7,24 -> 9,40 -> etc
129
130 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
135 A = any odd integer, so A^2 any odd square
136 B = (A^2-1)/2
137 C = (A^2+1)/2
138
139 / A^2-1 \ / A^2+1 \
140 A^2 + | ------ |^2 = | ----- |^2
141 \ 2 / \ 2 /
142
143 This is also described by Fibonacci (Liber Quadratorum) in terms of
144 sums of odd numbers
145
146 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
151 eg. s=25=A^2 B^2=((25-1)/2)^2=144 so A=5,B=12
152
153 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
158 ****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
166 See Math::PlanePath::Corner for a path following such gnomons.
167
168 A Repeatedly
169 Taking the middle "A" matrix repeatedly gives
170
171 3,4 -> 21,20 -> 119,120 -> 697,696 -> etc A,B legs
172
173 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
177 D Repeatedly
178 Taking the lower "D" matrix repeatedly gives
179
180 3,4 -> 15,8 -> 35,12 -> 63,16 -> etc A,B legs
181
182 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
186 A = k^2 - 1 k even >= 2 for primitives
187 B = 2*k
188 C = k^2 + 1 so C=A+2
189
190 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
195 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
201 tree_type => "UArD" coordinates A,B
202
203 ______________ 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
209 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
214 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
218 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
222 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
226 FB Tree
227 Option "tree_type => "FB"" selects a tree independently by
228
229 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
235 H. Lee Price, "The Pythagorean Tree: A New Species", 2008,
236 <http://arxiv.org/abs/0809.4324> (version 2)
237
238 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
245 tree_type => "FB"
246
247 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
264 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
268 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
271 tree_type => "FB" coordinates A,B
272
273 ______________ 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
279 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
283 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
291 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
295 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
301 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
305 tree_type => "UAD", digit_order => "LtoH"
306
307 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
327 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
331 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
335 AC Coordinates
336 Option "coordinates => 'AC'" gives the A and C legs of each triple as
337 X=A,Y=C.
338
339 coordinates => "AC"
340
341 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
366 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
370 For the FB tree the set of points visited is the same (of course), but
371 a different N numbering.
372
373 tree_type => "FB", coordinates => "AC"
374
375 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
400 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
405 coordinates => "BC"
406
407 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
436 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
441 For the FB tree, the set of points visited is the same of course, but a
442 different N numbering.
443
444 tree_type => "FB", coordinates => "BC"
445
446 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
475 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
479 A^2 = C^2 - B^2
480 = (C+B)*(C-B)
481
482 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
486 C+B = s^2 and conversely C = (s^2 + t^2)/2
487 C-B = t^2 B = (s^2 - t^2)/2
488
489 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
493 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
498 C + B = s^2 anti-diagonal 45-degrees,
499 position along diagonal determined by t
500
501 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
506 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
512 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
517 P = sqrt((C+A)/2)
518 Q = sqrt((C-A)/2)
519
520 The first P=2,Q=1 is the triple A=3,B=4,C=5.
521
522 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
526 tree_type => "UAD", coordinates => "PQ"
527
528 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
542 The diagonal N=1,2,5,14,41,etc is P=Q+1 as per "U Repeatedly" above.
543
544 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
550 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
555 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
561 coordinates => "SM"
562
563 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
589 SC Coordinates
590 Option "coordinates => 'SC'" gives the small leg and hypotenuse from
591 each triple,
592
593 coordinates => "SC"
594
595 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
620 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
623 MC Coordinates
624 Option "coordinates => 'MC'" gives the medium leg and hypotenuse from
625 each triple,
626
627 coordinates => "MC"
628
629 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
649 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
652 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
657 coordinates => "AB"
658
659 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
669 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
675 U triplet U,A,D
676 A
677 D
678
679 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
683 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
687 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
691 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
695 D^k .A wraparound A,D to U
696 D^k .D k>=0
697 U^(k+1).U
698
699 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
703 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
706 U^k P,Q -> (k+1)*P-k*Q, k*P-(k-1)*Q
707 D^k P,Q -> P+2k*Q, Q
708
709 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
713 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
718 coordinates => "BC"
719
720 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
731 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
741 "$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
746 "UAD" (the default)
747 "UArD" UAD with Gray code reflections
748 "FB"
749 "UMT"
750
751 The "coordinates" option can be
752
753 "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
761 The "digit_order" option can be
762
763 "HtoL" high to low (the default)
764 "LtoH" low to high (the default)
765
766 "$n = $path->n_start()"
767 Return 1, the first N in the path.
768
769 "($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
773 "$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
777 The return is "undef" if "$x,$y" is not a primitive Pythagorean
778 triple, per the "coordinates" option.
779
780 "$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
784 For coordinates=AB or SM, this is the hypotenuse C and therefore an
785 integer, for integer $n.
786
787 "($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
791 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
796 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
802 coordinate minimum
803 ---------- -------
804 A,S 3
805 B,M 4
806 C 5
807 P 2
808 Q 1
809
810 Tree Methods
811 Each point has 3 children, so the path is a complete ternary tree.
812
813 "@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
817 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
822 "$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
826 "$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
830 This is simply "floor(($n+1)/3)", reversing the "tree_n_children()"
831 calculation above.
832
833 "$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
838 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
842 "$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
848 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
854 "$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
862 U P -> 2P-Q ( 2 -1 )
863 Q -> P ( 1 0 )
864
865 A P -> 2P+Q ( 2 1 )
866 Q -> P ( 1 0 )
867
868 D P -> P+2Q ( 1 2 )
869 Q -> Q unchanged ( 0 1 )
870
871 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
875 Repeatedly applying "U" gives
876
877 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
884 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
887 U^k P=k+2, Q=k+1 start for k high zeros
888
889 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
893 M1 P -> P+Q ( 1 1 )
894 Q -> 2Q ( 0 2 )
895
896 M2 P -> 2P ( 2 0 )
897 Q -> P-Q ( 1 -1 )
898
899 M3 P -> 2P ( 2 0 )
900 Q -> P+Q ( 1 1 )
901
902 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
906 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
911 if P > 3Q reverse "D" P -> P-2Q
912 digit=2 Q -> unchanged
913
914 if P > 2Q reverse "A" P -> Q
915 digit=1 Q -> P-2Q
916
917 otherwise reverse "U" P -> Q
918 digit=0 Q -> 2Q-P
919
920 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
924 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
929 The conditions P>3Q or P>2Q work because each matrix sends its parent
930 P,Q to one of three disjoint regions,
931
932 Q P=Q P=2Q P=3Q
933 | * U ---- A ++++++
934 | * ---- ++++++
935 | * ---- ++++++
936 | * ---- ++++++
937 | * ---- ++++++
938 | * ---- ++++++
939 | * ---- ++++++ D
940 | * ----++++++
941 | * ----++++
942 | ----++
943 |
944 +------------------------------------------------- P
945
946 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
949 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
953 if P odd reverse M1 P -> P-Q
954 (Q even) Q -> Q/2
955
956 if P > 2Q reverse M2 P -> P/2
957 (P even) Q -> P/2 - Q
958
959 otherwise reverse M3 P -> P/2
960 (P even) Q -> Q - P/2
961
962 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
967 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
972 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
986 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
990 if P > 2Q reverse "U" P -> Q
991 digit=0 Q -> 2Q-P
992
993 if P even reverse "M2" P -> P/2
994 (Q odd) Q -> P/2 - Q
995
996 otherwise reverse "T" P -> P - 3 * Q/2
997 (Q even) Q -> Q/2
998
999 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
1003 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
1017 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
1024 Amin = 2*level + 1
1025 Bmin = 4*level
1026
1027 In P,Q coordinates the same topmost line is the smallest P and bottom-
1028 most the smallest Q. The values are
1029
1030 Pmin = level+1
1031 Qmin = 1
1032
1033 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
1038 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
1044 Amin = 2^level + 1
1045 Bmin = 2^level + 4
1046
1047 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
1052 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
1056 The fixed Q=1 arises from the M1 steps giving
1057
1058 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
1063 followed by M2 step
1064 Q -> P-Q
1065 = 1
1066
1067 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
1074 <http://oeis.org/A007051> (etc)
1075
1076 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
1080 A058529 possible values taken by abs(A-B),
1081 being integers with all prime factors == +/-1 mod 8
1082
1083 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
1092 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
1098 "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
1103 "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
1112 "D" repeatedly
1113 A000466 leg A, being 4*n^2-1 for n>=1
1114
1115 "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
1120 "M2" repeatedly
1121 A015249 \ leg A, binary 111000111000...
1122 A084152 |
1123 A084175 /
1124 A054881 leg B, binary 1010..1010000..00
1125
1126 "M3" repeatedly
1127 A106624 P,Q pairs, 2^k-1,2^k
1128
1129 "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
1149 This file is part of Math-PlanePath.
1150
1151 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
1156 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
1161 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/>.
1163
1164
1165
1166perl v5.36.0 2022-07-22Math::PlanePath::PythagoreanTree(3)