1Math::PlanePath::PythagUosreeranCTorneter(i3b)uted PerlMDaotchu:m:ePnltaanteiPoanth::PythagoreanTree(3)
2
3
4

NAME

6       Math::PlanePath::PythagoreanTree -- primitive Pythagorean triples by
7       tree
8

SYNOPSIS

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

DESCRIPTION

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, et al
21           "FB"     Price
22           "UMT"    a third form
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  all integers
36
37               <-A->
38
39       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
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           depth=0   depth=1    depth=2    depth=3
95            N=1      N=2..4     N=5..13    N=14...
96
97                             +-> 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
109       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
112           Nrow = 1 + (1 + 3 + 3^2 + ... + 3^(depth-1))
113                = (3^depth + 1) / 2
114
115       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
118                +--------+---------+---------+--   --+---------+
119           N =  | binary | ternary | ternary |  ...  | ternary |
120                +--------+---------+---------+--   --+---------+
121                     1      0,1,2     0,1,2             0,1,2
122
123       The number of ternary digits is the "depth" and their value without the
124       high binary 1 is the position in the row.
125
126   A Repeatedly
127       Taking the middle "A" matrix repeatedly gives
128
129           3,4 -> 21,20 -> 119,120 -> 697,696 -> etc
130
131       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
135   D Repeatedly
136       Taking the lower "D" matrix repeatedly gives
137
138          3,4 -> 15,8 -> 35,12 -> 63,16 -> etc
139
140       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
144            A = k^2-1       k even for primitives
145            B = 2*k
146            C = k^2+1       so C=A+2
147
148       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
153   U Repeatedly
154       Taking the upper "U" matrix repeatedly gives
155
156           3.4 -> 5,12 -> 7,24 -> 9,40 -> etc
157
158       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
163           A = any odd integer, so A^2 any odd square
164           B = (A^2-1)/2
165           C = (A^2+1)/2
166
167                  / A^2-1 \       / A^2+1 \
168           A^2 + | ------  |^2 = |  -----  |^2
169                  \   2   /       \   2   /
170
171       This is also described by Fibonacci in his Liber Quadratorum (Book of
172       Squares) in terms of sums of odd numbers
173
174           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
179           eg. s=25=A^2  B^2=((25-1)/2)^2=144  so A=5,B=12
180
181       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
186              *****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
194       See Math::PlanePath::Corner for a path following such gnomons.
195
196   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
202                             +-> 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
214       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
219       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
223       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
227       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
231   FB Tree
232       Option "tree_type => "FB"" selects a tree independently by
233
234           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
240           H. Lee Price, "The Pythagorean Tree: A New Species", 2008,
241           <http://arxiv.org/abs/0809.4324> (version 2)
242
243       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
250           tree_type => "FB"
251
252           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
269       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
273       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
276           N=1      N=2..4      N=5..13     N=14...
277
278                             +-> 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
290   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
294                     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
306       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
310   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
316       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
320           tree_type => "UAD", digit_order => "LtoH"
321
322           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
342       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
346       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
350   AC Coordinates
351       Option "coordinates => 'AC'" gives the A and C legs of each triple as
352       X=A,Y=C.
353
354           coordinates => "AC"
355
356            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
381       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
385       For the FB tree the set of points visited is the same, but with a
386       different N numbering.
387
388           tree_type => "FB", coordinates => "AC"
389
390            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
415   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
420           coordinates => "BC"
421
422           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
451       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
456       For the FB tree the set of points visited is the same, but with a
457       different N numbering.
458
459           tree_type => "FB", coordinates => "BC"
460
461           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
490       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
494           A^2 = C^2 - B^2
495               = (C+B)*(C-B)
496
497       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
501           C+B = s^2    and conversely  C = (s^2 + t^2)/2
502           C-B = t^2                    B = (s^2 - t^2)/2
503
504             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
508       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
513            C + B = s^2      anti-diagonal 45-degrees,
514                             position along diagonal determined by t
515
516       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
521   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
527           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
532           P = sqrt((C+A)/2)
533           Q = sqrt((C-A)/2)
534
535       The first P=2,Q=1 is the triple A=3,B=4,C=5.
536
537       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
541           tree_type => "UAD", coordinates => "PQ"
542
543            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
557       The diagonal N=1,2,5,14,41,etc is P=Q+1 as per "U Repeatedly" above.
558
559       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
565       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
570   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
576           coordinates => "SM"
577
578            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
604   SC Coordinates
605       Option "coordinates => 'SC'" gives the small leg and hypotenuse from
606       each triple,
607
608           coordinates => "SC"
609
610            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
635       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
638   MC Coordinates
639       Option "coordinates => 'MC'" gives the medium leg and hypotenuse from
640       each triple,
641
642           coordinates => "MC"
643
644            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
664       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
667   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
672           coordinates => "AB"
673
674           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
684       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
690           U              triplet U,A,D
691           A
692           D
693
694           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
698           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
702           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
706           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
710           D^k    .A      wraparound A,D to U
711           D^k    .D       k>=0
712           U^(k+1).U
713
714           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
718       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
721           U^k    P,Q   ->  (k+1)*P-k*Q, k*P-(k-1)*Q
722           D^k    P,Q   ->  P+2k*Q, Q
723
724       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
728   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
733           coordinates => "BC"
734
735           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
746       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

FUNCTIONS

753       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
754       classes.
755
756       "$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
761               "UAD"         (the default)
762               "UArD"        UAD with Gray code reflections
763               "FB"
764               "UMT"
765
766           The "coordinates" option can be
767
768               "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
776           The "digit_order" option can be
777
778               "HtoL"   high to low (the default)
779               "LtoH"   low to high (the default)
780
781       "$n = $path->n_start()"
782           Return 1, the first N in the path.
783
784       "($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
788       "$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
792           The return is "undef" if "$x,$y" is not a primitive Pythagorean
793           triple, per the "coordinates" option.
794
795       "$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
799           For coordinates=AB or SM this is the hypotenuse C and therefore an
800           integer, for integer $n.
801
802       "($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
806           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
811   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
817               coordinate    minimum
818               ----------    -------
819                   A,S          3
820                   B,M          4
821                    C           5
822                    P           2
823                    Q           1
824
825   Tree Methods
826       Each point has 3 children, so the path is a complete ternary tree.
827
828       "@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
832           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
837       "$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
841       "$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
845           This is simply "floor(($n+1)/3)", reversing the "tree_n_children()"
846           calculation above.
847
848       "$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
853           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
857       "$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
863   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
869       "$bool = $path->tree_any_leaf()"
870           Return false, since there are no leaf nodes in the tree.
871

FORMULAS

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
877           U     P -> 2P-Q            ( 2 -1 )
878                 Q -> P               ( 1  0 )
879
880           A     P -> 2P+Q            ( 2  1 )
881                 Q -> P               ( 1  0 )
882
883           D     P -> P+2Q            ( 1  2 )
884                 Q -> Q unchanged     ( 0  1 )
885
886       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
890       Repeatedly applying "U" gives
891
892           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
899       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
902           U^k    P=k+2, Q=k+1       start for k high zeros
903
904   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
908           M1     P -> P+Q         ( 1  1 )
909                  Q -> 2Q          ( 0  2 )
910
911           M2     P -> 2P          ( 2  0 )
912                  Q -> P-Q         ( 1 -1 )
913
914           M3     P -> 2P          ( 2  0 )
915                  Q -> P+Q         ( 1  1 )
916
917       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
921   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
926           if P > 3Q    reverse "D"   P -> P-2Q
927                         digit=2      Q -> unchanged
928
929           if P > 2Q    reverse "A"   P -> Q
930                         digit=1      Q -> P-2Q
931
932           otherwise    reverse "U"   P -> Q
933                         digit=0      Q -> 2Q-P
934
935       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
939       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
944       The conditions P>3Q or P>2Q work because each matrix sends its parent
945       P,Q to one of three disjoint regions,
946
947            Q                  P=Q                    P=2Q                P=3Q
948            |                    *       U         ----     A        ++++++
949            |                  *               ----            ++++++
950            |                *             ----          ++++++
951            |              *           ----        ++++++
952            |            *         ----      ++++++
953            |          *       ----    ++++++
954            |        *     ----  ++++++                     D
955            |      *   ----++++++
956            |    * ----++++
957            |  ----++
958            |
959            +------------------------------------------------- P
960
961       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
964   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
968           if P odd     reverse M1    P -> P-Q
969           (Q even)                   Q -> Q/2
970
971           if P > 2Q    reverse M2    P -> P/2
972           (P even)                   Q -> P/2 - Q
973
974           otherwise    reverse M3    P -> P/2
975           (P even)                   Q -> Q - P/2
976
977       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
982       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
987            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
1001   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
1005           if P > 2Q    reverse "U"     P -> Q
1006                         digit=0        Q -> 2Q-P
1007
1008           if P even    reverse "M2"    P -> P/2
1009           (Q odd)                      Q -> P/2 - Q
1010
1011           otherwise    reverse "T"     P -> P - 3 * Q/2
1012           (Q even)                     Q -> Q/2
1013
1014       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
1018            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
1032   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
1039           Amin = 2*level + 1
1040           Bmin = 4*level
1041
1042       In P,Q coordinates the same topmost line is the smallest P and bottom-
1043       most the smallest Q.  The values are
1044
1045           Pmin = level+1
1046           Qmin = 1
1047
1048       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
1053   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
1059           Amin = 2^level + 1
1060           Bmin = 2^level + 4
1061
1062       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
1067           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
1071       The fixed Q=1 arises from the M1 steps giving
1072
1073           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
1078           followed by M2 step
1079           Q -> P-Q
1080                = 1
1081
1082       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

OEIS

1086       Entries in Sloane's Online Encyclopedia of Integer Sequences related to
1087       this path include,
1088
1089           <http://oeis.org/A007051> (etc)
1090
1091           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
1095           A058529   possible values taken by abs(A-B),
1096                       being integers with all prime factors == +/-1 mod 8
1097
1098           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
1103           "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
1108           "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
1117           "D" repeatedly
1118             A000466    coordinate A, being 4*n^2-1 for n>=1
1119
1120           "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
1125           "M2" repeatedly
1126             A015249    \ coordinate A, binary 111000111000...
1127             A084152    |
1128             A084175    /
1129             A054881    coordinate B, binary 1010..1010000..00
1130
1131           "M3" repeatedly
1132             A106624    coordinate P,Q pairs, 2^k-1,2^k
1133
1134           "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

SEE ALSO

1144       Math::PlanePath, Math::PlanePath::Hypot,
1145       Math::PlanePath::RationalsTree, Math::PlanePath::CoprimeColumns
1146

HOME PAGE

1148       <http://user42.tuxfamily.org/math-planepath/index.html>
1149

LICENSE

1151       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
1152
1153       This file is part of Math-PlanePath.
1154
1155       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
1160       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
1165       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/>.
1167
1168
1169
1170perl v5.32.0                      2020-07-28Math::PlanePath::PythagoreanTree(3)
Impressum