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, 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

FUNCTIONS

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

FORMULAS

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

OEIS

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

SEE ALSO

1139       Math::PlanePath, Math::PlanePath::Hypot,
1140       Math::PlanePath::RationalsTree, Math::PlanePath::CoprimeColumns
1141

HOME PAGE

1143       <http://user42.tuxfamily.org/math-planepath/index.html>
1144

LICENSE

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.32.1                      2021-01-27Math::PlanePath::PythagoreanTree(3)
Impressum