.\" Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28) .\" .\" Standard preamble: .\" ======================================================================== .de Sp \" Vertical space (when we can't use .PP) .if t .sp .5v .if n .sp .. .de Vb \" Begin verbatim text .ft CW .nf .ne \\$1 .. .de Ve \" End verbatim text .ft R .fi .. .\" Set up some character translations and predefined strings. \*(-- will .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left .\" double quote, and \*(R" will give a right double quote. \*(C+ will .\" give a nicer C++. Capital omega is used to do unbreakable dashes and .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff, .\" nothing in troff, for use with C<>. .tr \(*W- .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' .ie n \{\ . ds -- \(*W- . ds PI pi . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch . ds L" "" . ds R" "" . ds C` "" . ds C' "" 'br\} .el\{\ . ds -- \|\(em\| . ds PI \(*p . ds L" `` . ds R" '' . ds C` . ds C' 'br\} .\" .\" Escape single quotes in literal strings from groff's Unicode transform. .ie \n(.g .ds Aq \(aq .el .ds Aq ' .\" .\" If the F register is turned on, we'll generate index entries on stderr for .\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index .\" entries marked with X<> in POD. Of course, you'll have to process the .\" output yourself in some meaningful fashion. .\" .\" Avoid warning from groff about undefined register 'F'. .de IX .. .nr rF 0 .if \n(.g .if rF .nr rF 1 .if (\n(rF:(\n(.g==0)) \{ . if \nF \{ . de IX . tm Index:\\$1\t\\n%\t"\\$2" .. . if !\nF==2 \{ . nr % 0 . nr F 2 . \} . \} .\} .rr rF .\" .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2). .\" Fear. Run. Save yourself. No user-serviceable parts. . \" fudge factors for nroff and troff .if n \{\ . ds #H 0 . ds #V .8m . ds #F .3m . ds #[ \f1 . ds #] \fP .\} .if t \{\ . ds #H ((1u-(\\\\n(.fu%2u))*.13m) . ds #V .6m . ds #F 0 . ds #[ \& . ds #] \& .\} . \" simple accents for nroff and troff .if n \{\ . ds ' \& . ds ` \& . ds ^ \& . ds , \& . ds ~ ~ . ds / .\} .if t \{\ . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u" . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u' . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u' . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u' . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u' . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u' .\} . \" troff and (daisy-wheel) nroff accents .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V' .ds 8 \h'\*(#H'\(*b\h'-\*(#H' .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#] .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H' .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u' .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#] .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#] .ds ae a\h'-(\w'a'u*4/10)'e .ds Ae A\h'-(\w'A'u*4/10)'E . \" corrections for vroff .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u' .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u' . \" for low resolution devices (crt and lpr) .if \n(.H>23 .if \n(.V>19 \ \{\ . ds : e . ds 8 ss . ds o a . ds d- d\h'-1'\(ga . ds D- D\h'-1'\(hy . ds th \o'bp' . ds Th \o'LP' . ds ae ae . ds Ae AE .\} .rm #[ #] #H #V #F C .\" ======================================================================== .\" .IX Title "Math::PlanePath::PythagoreanTree 3pm" .TH Math::PlanePath::PythagoreanTree 3pm "2014-08-30" "perl v5.20.1" "User Contributed Perl Documentation" .\" For nroff, turn off justification. Always turn off hyphenation; it makes .\" way too many mistakes in technical documents. .if n .ad l .nh .SH "NAME" Math::PlanePath::PythagoreanTree \-\- primitive Pythagorean triples by tree .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 5 \& use Math::PlanePath::PythagoreanTree; \& my $path = Math::PlanePath::PythagoreanTree\->new \& (tree_type => \*(AqUAD\*(Aq, \& coordinates => \*(AqAB\*(Aq); \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This path enumerates primitive Pythagorean triples by a breadth-first traversal of one of three ternary trees, .PP .Vb 3 \& "UAD" Berggren, Barning, Hall, et al \& "FB" Price \& "UMT" a third form .Ve .PP Each X,Y point is a pair of integer A,B sides of a right triangle. The points are \*(L"primitive\*(R" in the sense that the sense that A and B have no common factor. .PP .Vb 2 \& A^2 + B^2 = C^2 gcd(A,B)=1, no common factor \& X=A, Y=B \& \& ^ * ^ \& / /| | right triangle \& C / | B A side odd \& / / | | B side even \& v *\-\-\-* v C hypotenuse all integers \& \& <\-A\-> .Ve .PP A primitive triple always has one of A,B odd and the other even. The trees here have triples ordered as A odd and B even. .PP The trees are traversed breadth-first and tend to go out to rather large A,B values while yet to complete smaller ones. The \s-1UAD\s0 tree goes out further than the \s-1FB. \s0 See the author's mathematical write-up for more properties. .Sp .RS 4 .RE .SS "\s-1UAD\s0 Tree" .IX Subsection "UAD Tree" The \s-1UAD\s0 tree by Berggren (1934) and later independently by Barning (1963), Hall (1970), and other authors, uses three matrices U, A and D which can be multiplied onto an existing primitive triple to form three further new primitive triples. .PP .Vb 1 \& tree_type => "UAD" (the default) \& \& Y=40 | 14 \& | \& | \& | \& | 7 \& Y=24 | 5 \& | \& Y=20 | 3 \& | \& Y=12 | 2 13 \& | \& | 4 \& Y=4 | 1 \& | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=3 X=15 X=20 X=35 X=45 .Ve .PP The \s-1UAD\s0 matrices are .PP .Vb 3 \& 1 \-2 2 1 2 2 \-1 2 2 \& U = 2 \-1 2 A = 2 1 2 D = \-2 1 2 \& 2 \-2 3 2 2 3 \-2 2 3 .Ve .PP They're multiplied on the right of an (A,B,C) column vector, for example .PP .Vb 3 \& / 3 \e / 5 \e \& U * | 4 | = | 12 | \& \e 5 / \e 13 / .Ve .PP The starting point is N=1 at X=3,Y=4 which is the well-known triple .PP .Vb 1 \& 3^2 + 4^2 = 5^2 .Ve .PP From it three further points N=2, N=3 and N=4 are derived, then three more from each of those, etc, .PP .Vb 2 \& depth=0 depth=1 depth=2 depth=3 \& N=1 N=2..4 N=5..13 N=14... \& \& +\-> 7,24 A,B coordinates \& +\-> 5,12 \-\-+\-> 55,48 \& | +\-> 45,28 \& | \& | +\-> 39,80 \& 3,4 \-\-+\-> 21,20 \-\-+\-> 119,120 \& | +\-> 77,36 \& | \& | +\-> 33,56 \& +\-> 15,8 \-\-+\-> 65,72 \& +\-> 35,12 .Ve .PP Counting N=1 as depth=0, each level has 3^depth many points and the first N of a level (\f(CW\*(C`tree_depth_to_n()\*(C'\fR) is at .PP .Vb 2 \& Nrow = 1 + (1 + 3 + 3^2 + ... + 3^(depth\-1)) \& = (3^depth + 1) / 2 .Ve .PP The level numbering is like a mixed-radix representation of N where the high digit is binary (so always 1) and the digits below are ternary. .PP .Vb 4 \& +\-\-\-\-\-\-\-\-+\-\-\-\-\-\-\-\-\-+\-\-\-\-\-\-\-\-\-+\-\- \-\-+\-\-\-\-\-\-\-\-\-+ \& N = | binary | ternary | ternary | ... | ternary | \& +\-\-\-\-\-\-\-\-+\-\-\-\-\-\-\-\-\-+\-\-\-\-\-\-\-\-\-+\-\- \-\-+\-\-\-\-\-\-\-\-\-+ \& 1 0,1,2 0,1,2 0,1,2 .Ve .PP The number of ternary digits is the \*(L"depth\*(R" and their value without the high binary 1 is the position in the row. .SS "A Repeatedly" .IX Subsection "A Repeatedly" Taking the middle \*(L"A\*(R" matrix repeatedly gives .PP .Vb 1 \& 3,4 \-> 21,20 \-> 119,120 \-> 697,696 \-> etc .Ve .PP which are the triples with legs A,B differing by 1 and therefore just above or below the X=Y leading diagonal. The N values are 1,3,9,27,etc = 3^depth. .SS "D Repeatedly" .IX Subsection "D Repeatedly" Taking the lower \*(L"D\*(R" matrix repeatedly gives .PP .Vb 1 \& 3,4 \-> 15,8 \-> 35,12 \-> 63,16 \-> etc .Ve .PP which is the primitives among a sequence of triples known to the ancients (Dickson's \fIHistory of the Theory of Numbers\fR, start of chapter \s-1IV\s0), .PP .Vb 3 \& A = k^2\-1 k even for primitives \& B = 2*k \& C = k^2+1 so C=A+2 .Ve .PP When k is even these are primitive. If k is odd then A and B are both even, ie. a common factor of 2, so not primitive. These points are the last of each level, so at N=(3^(depth+1)\-1)/2 which is \f(CW\*(C`tree_depth_to_n_end()\*(C'\fR. .SS "U Repeatedly" .IX Subsection "U Repeatedly" Taking the upper \*(L"U\*(R" matrix repeatedly gives .PP .Vb 1 \& 3.4 \-> 5,12 \-> 7,24 \-> 9,40 \-> etc .Ve .PP with C=B+1 and A the odd numbers. These are the first of each level so at Nrow described above. The resulting triples are a sequence known to Pythagoras (Dickson's \fIHistory of the Theory of Numbers\fR, start of chapter \&\s-1IV\s0). .PP .Vb 3 \& A = any odd integer, so A^2 any odd square \& B = (A^2\-1)/2 \& C = (A^2+1)/2 \& \& / A^2\-1 \e / A^2+1 \e \& A^2 + | \-\-\-\-\-\- |^2 = | \-\-\-\-\- |^2 \& \e 2 / \e 2 / .Ve .PP This is also described by Fibonacci in his \&\fILiber Quadratorum\fR (\fIBook of Squares\fR) in terms of sums of odd numbers .IX Xref "Fibonacci Liber Quadratorum Book of Squares" .PP .Vb 4 \& s = any odd square = A^2 \& B^2 = 1 + 3 + 5 + ... + s\-2 = ((s\-1)/2)^2 \& C^2 = 1 + 3 + 5 + ... + s\-2 + s = ((s+1)/2)^2 \& so C^2 = A^2 + B^2 \& \& eg. s=25=A^2 B^2=((25\-1)/2)^2=144 so A=5,B=12 .Ve .PP The geometric interpretation is that an existing square of side B is extended by a \*(L"gnomon\*(R" around two sides making a new larger square of side C=B+1. The length of the gnomon is odd and when it's an odd square then the new total area is the sum of two squares. .IX Xref "Gnomon Gnomon" .PP .Vb 7 \& *****gnomon******* gnomon length an odd square = A^2 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-+ * \& | | * so new bigger square area \& | square | * C^2 = A^2 + B^2 \& | with side B | * \& | | * \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-+ * .Ve .PP See Math::PlanePath::Corner for a path following such gnomons. .SS "UArD Tree" .IX Subsection "UArD Tree" Option \f(CW\*(C`tree_type => "UArD"\*(C'\fR varies the \s-1UAD\s0 tree by applying a left-right reflection under each \*(L"A\*(R" matrix. The result is ternary reflected Gray code order. The 3 children under each node are unchanged, just their order. .IX Xref "Gray code" .PP .Vb 11 \& +\-> 7,24 tree_type => "UArD" \& +\-> 5,12 \-\-+\-> 55,48 A,B coordinates \& | +\-> 45,28 \& | \& | +\-> 77,36 <\-+\- U,D legs swapped \& 3,4 \-\-+\-> 21,20 \-\-+\-> 119,120 | \& | +\-> 39,80 <\-+ \& | \& | +\-> 33,56 \& +\-> 15,8 \-\-+\-> 65,72 \& +\-> 35,12 .Ve .PP Notice the middle points 77,36 and 39,80 are swapped relative to the \s-1UAD\s0 shown above. In general the whole tree underneath an \*(L"A\*(R" is mirrored. If there's an even number of \*(L"A\*(R"s above then those mirrorings cancel out to be plain again. .PP This tree form is primarily of interest for \*(L"Digit Order Low to High\*(R" described below since it gives points in order clockwise down from the Y axis. .PP In \*(L"\s-1PQ\s0 Coordinates\*(R" below, with the default digits high to low, UArD also makes successive steps across the row either horizontal or 45\-degrees NE-SW. .PP In all cases the Gray coding is applied to N first, then the resulting digits are interpreted either high to low (the default) or low to high (\f(CW\*(C`LtoH\*(C'\fR option). .SS "\s-1FB\s0 Tree" .IX Subsection "FB Tree" Option \f(CW\*(C`tree_type => "FB"\*(C'\fR selects a tree independently by .IX Xref "Firstov, V. E. Price, H. Lee" .Sp .RS 4 V. E. Firstov, \*(L"A Special Matrix Transformation Semigroup of Primitive Pairs and the Genealogy of Pythagorean Triples\*(R", Matematicheskie Zametki, 2008, volume 84, number 2, pages 281\-299 (in Russian), and Mathematical Notes, 2008, volume 84, number 2, pages 263\-279 (in English) .Sp H. Lee Price, \*(L"The Pythagorean Tree: A New Species\*(R", 2008, (version 2) .RE .PP Firstov finds this tree by semigroup transformations. Price finds it by expressing triples in certain \*(L"Fibonacci boxes\*(R" with a box of four values q',q,p,p' having p=q+q' and p'=p+q so each is the sum of the preceding two in a fashion similar to the Fibonacci sequence. A box where p and q have no common factor corresponds to a primitive triple. See \*(L"\s-1PQ\s0 Coordinates\*(R" and \&\*(L"\s-1FB\s0 Transformations\*(R" below. .PP .Vb 1 \& tree_type => "FB" \& \& Y=40 | 5 \& | \& | \& | \& | 17 \& Y=24 | 4 \& | \& | 8 \& | \& Y=12 | 2 6 \& | \& | 3 \& Y=4 | 1 \& | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=3 X=15 x=21 X=35 .Ve .PP For a given box three transformations can be applied to go to new boxes corresponding to new primitive triples. This visits all and only primitive triples, but in a different order to the \s-1UAD\s0 above. .PP The first point N=1 is again at X=3,Y=4, from which three further points N=2,3,4 are derived, then three more from each of those, etc. .PP .Vb 1 \& N=1 N=2..4 N=5..13 N=14... \& \& +\-> 9,40 A,B coordinates \& +\-> 5,12 \-\-+\-> 35,12 \& | +\-> 11,60 \& | \& | +\-> 21,20 \& 3,4 \-\-+\-> 15,8 \-\-+\-> 55,48 \& | +\-> 39,80 \& | \& | +\-> 13,84 \& +\-> 7,24 \-\-+\-> 63,16 \& +\-> 15,112 .Ve .SS "\s-1UMT\s0 Tree" .IX Subsection "UMT Tree" Option \f(CW\*(C`tree_type =\*(C'\fR \*(L"\s-1UMT\*(R"\s0> is a third tree type by Firstov (reference above). It's a combination of \*(L"U\*(R", \*(L"M2\*(R" and a third matrix T = M1*D. .IX Xref "Firstov, V. E." .PP .Vb 11 \& U +\-> 7,24 A,B coordinates \& +\-> 5,12 \-\-+\-> 35,12 \& | +\-> 65,72 \& | \& | M2 +\-> 33,56 \& 3,4 \-\-+\-> 15,8 \-\-+\-> 55,48 \& | +\-> 45,28 \& | \& | T +\-> 39,80 \& +\-> 21,20 \-\-+\-> 91,60 \& +\-> 105,88 .Ve .PP The first \*(L"T\*(R" child 21,20 is the same as the \*(L"A\*(R" matrix, but it differs at further levels down. For example \*(L"T\*(R" twice is 105,88 which is not the same as \*(L"A\*(R" twice 119,120. .SS "Digit Order Low to High" .IX Subsection "Digit Order Low to High" Option \f(CW\*(C`digit_order => \*(AqLtoH\*(Aq\*(C'\fR applies matrices using the ternary digits of N taken from low to high. The points in each row are unchanged, as is the parent-child N numbering, but the X,Y values are rearranged within the row. .PP The \s-1UAD\s0 matrices send points to disjoint regions and the effect of LtoH is to keep the tree growing into those separate wedge regions. The arms grow roughly as follows .PP .Vb 1 \& tree_type => "UAD", digit_order => "LtoH" \& \& Y=80 | 6 UAD LtoH \& | / \& | / \& Y=56 | / 7 10 9 \& | / / / / \& | / / | / 8 \& | / _/ / / / \& | / / / / / \& Y=24 | 5 / / | / _/ _\|_\-\-11 \& | / / _/ |/_/ _\|_\-\- \& Y=20 | / / / _\|_3 _\|_\-\- _\|_\|_\|_\|_\-\-\-\-12 \& | |/_/ _\|_\-\- _\|_\-\-\- _\|_\|_\|_\-\-\-\-\- \& Y=12 | 2 _\|_\-\- _/_\|_\|_\-\-\-\- _\|_\|_\|_13 \& | / _\|_\-\- _\|_\-\- _\|_\|_\|_\|_\-\-\-\-\- \& | /_\-\-_\|_\|_\|_\|_\-\-\-4\-\-\-\-\- \& Y=4 | 1\-\-\- \& | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=3 X=15 X=20 X=35 X=76 .Ve .PP Notice the points of the second row N=5 to N=13 are almost clockwise down from the Y axis, except N=8,9,10 go upwards. Those N=8,9,10 go upwards because the A matrix has a reflection (its determinant is \-1). .PP Option \f(CW\*(C`tree_type => "UArD"\*(C'\fR reverses the tree underneath each A, and that plus LtoH gives A,B points going clockwise in each row. P,Q coordinates go clockwise too. .SS "\s-1AC\s0 Coordinates" .IX Subsection "AC Coordinates" Option \f(CW\*(C`coordinates => \*(AqAC\*(Aq\*(C'\fR gives the A and C legs of each triple as X=A,Y=C. .PP .Vb 1 \& coordinates => "AC" \& \& 85 | 122 10 \& | \& | \& 73 | 6 \& | \& 65 | 11 40 \& 61 | 41 \& | \& | 7 \& | \& | \& 41 | 14 \& | 13 \& 35 | \& | 3 \& 25 | 5 \& | \& 17 | 4 \& 13 | 2 \& | \& Y=5 | 1 \& | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=3 7 9 21 35 45 55 63 77 .Ve .PP Since A "FB", coordinates => "AC" \& \& 85 | 11 35 \& | \& | \& 73 | 9 \& | \& 65 | 23 12 \& 61 | 7 \& | \& | 17 \& | \& | \& 41 | 5 \& | 6 \& 35 | \& | 8 \& 25 | 4 \& | \& 17 | 3 \& 13 | 2 \& | \& Y=5 | 1 \& | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=3 7 9 21 35 45 55 63 77 .Ve .SS "\s-1BC\s0 Coordinates" .IX Subsection "BC Coordinates" Option \f(CW\*(C`coordinates => \*(AqBC\*(Aq\*(C'\fR gives the B and C legs of each triple as X=B,Y=C. This is the B=even and C=long legs of all primitive triples. This combination has points on 45\-degree straight lines. .PP .Vb 1 \& coordinates => "BC" \& \& 101 | 121 \& 97 | 12 \& | \& 89 | 8 \& 85 | 10 122 \& | \& | \& 73 | 6 \& | \& 65 | 40 11 \& 61 | 41 \& | \& | 7 \& | \& | \& 41 | 14 \& | 13 \& 35 | \& | 3 \& 25 | 5 \& | \& 17 | 4 \& 13 | 2 \& | \& Y=5 | 1 \& | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=4 12 24 40 60 84 .Ve .PP Since B "FB", coordinates => "BC" \& \& 101 | 15 \& 97 | 50 \& | \& 89 | 10 \& 85 | 35 11 \& | \& | \& 73 | 9 \& | \& 65 | 12 23 \& 61 | 7 \& | \& | 17 \& | \& | \& 41 | 5 \& | 6 \& 35 | \& | 8 \& 25 | 4 \& | \& 17 | 3 \& 13 | 2 \& | \& Y=5 | 1 \& | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=4 12 24 40 60 84 .Ve .PP As seen from the diagrams, the B,C points fall on 45\-degree straight lines going up from X=Y\-1. This occurs because a primitive triple A,B,C with A odd and B even can be written .PP .Vb 2 \& A^2 = C^2 \- B^2 \& = (C+B)*(C\-B) .Ve .PP gcd(A,B)=1 means also gcd(C+B,C\-B)=1 and so since C+B and C\-B have no common factor they must each be squares to give A^2. Call them s^2 and t^2, .PP .Vb 2 \& C+B = s^2 and conversely C = (s^2 + t^2)/2 \& C\-B = t^2 B = (s^2 \- t^2)/2 \& \& s = odd integer s >= 3 \& t = odd integer s > t >= 1 \& with gcd(s,t)=1 so that gcd(C+B,C\-B)=1 .Ve .PP When t=1 this is C=(s^2+1)/2 and B=(s^2\-1)/2 which is the \*(L"U\*(R"\-repeated points at Y=X+1 for each s. As t increases the B,C coordinate combination makes a line upwards at 45\-degrees from those t=1 positions, .PP .Vb 2 \& C + B = s^2 anti\-diagonal 45\-degrees, \& position along diagonal determined by t .Ve .PP All primitive triples start from a C=B+1 with C=(s^2+1)/2 half an odd square, and go up from there. To ensure the triple is primitive must have gcd(s,t)=1. Values of t where gcd(s,t)!=1 are gaps in the anti-diagonal lines. .SS "\s-1PQ\s0 Coordinates" .IX Subsection "PQ Coordinates" Primitive Pythagorean triples can be parameterized as follows for A odd and B even. This is per Diophantus, and anonymous Arabic manuscript for constraining it to primitive triples (Dickson's \fIHistory of the Theory of Numbers\fR). .PP .Vb 4 \& A = P^2 \- Q^2 \& B = 2*P*Q \& C = P^2 + Q^2 \& with P > Q >= 1, one odd, one even, and no common factor \& \& P = sqrt((C+A)/2) \& Q = sqrt((C\-A)/2) .Ve .PP The first P=2,Q=1 is the triple A=3,B=4,C=5. .PP Option \f(CW\*(C`coordinates => \*(AqPQ\*(Aq\*(C'\fR gives these as X=P,Y=Q, for either \&\f(CW\*(C`tree_type\*(C'\fR. Because P>Q>=1 the values fall in the eighth of the plane below the X=Y diagonal, .PP .Vb 1 \& tree_type => "UAD", coordinates => "PQ" \& \& 10 | 9842 \& 9 | 3281 \& 8 | 1094 23 \& 7 | 365 32 \& 6 | 122 38 \& 5 | 41 8 \& 4 | 14 11 12 15 \& 3 | 5 6 16 \& 2 | 2 3 7 10 22 \& 1 | 1 4 13 40 121 \& Y=0 | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 8 9 10 11 .Ve .PP The diagonal N=1,2,5,14,41,etc is P=Q+1 as per \*(L"U Repeatedly\*(R" above. .PP The one-to-one correspondence between P,Q and A,B means both tree types visit all P,Q pairs, so all X,Y with no common factor and one odd one even. There's other ways to iterate through such coprime pairs and any such method would generate Pythagorean triples too, in a different order from the trees here. .PP The letters P and Q here are a little bit arbitrary. This parameterization is often written m,n or u,v but don't want \*(L"n\*(R" to be confused that with N point numbering or \*(L"u\*(R" to be confused with the U matrix. .SS "\s-1SM\s0 Coordinates" .IX Subsection "SM Coordinates" Option \f(CW\*(C`coordinates => \*(AqSM\*(Aq\*(C'\fR gives the small and medium legs from each triple as X=small,Y=medium. This is like \*(L"\s-1AB\*(R"\s0 except that if A>B then they're swapped to X=B,Y=A so X "SM" \& \& 91 | 16 \& 84 | 122 \& | 8 \& | 10 \& 72 | 12 \& | \& | \& 60 | 41 40 \& | 11 \& 55 | 6 \& | \& | 7 \& 40 | 14 \& | \& 35 | 13 \& | \& 24 | 5 \& 21 | 3 \& | \& 12 | 2 4 \& | \& Y=4 | 1 \& | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=3 8 20 33 48 60 65 .Ve .SS "\s-1SC\s0 Coordinates" .IX Subsection "SC Coordinates" Option \f(CW\*(C`coordinates => \*(AqSC\*(Aq\*(C'\fR gives the small leg and hypotenuse from each triple, .PP .Vb 1 \& coordinates => "SC" \& \& 85 | 122 10 \& | \& | \& 73 | 6 \& | \& | 40 11 \& 61 | 41 \& | \& 53 | 7 \& | \& | \& 41 | 14 \& 37 | 13 \& | \& | 3 \& 25 | 5 \& | \& | 4 \& 13 | 2 \& | \& Y=5 | 1 \& | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=3 8 20 33 48 .Ve .PP The points are all X < 0.7*Y since with X as the smaller leg must have X^2\ <\ Y^2/2 so X\ <\ Y*1/\fIsqrt\fR\|(2). .SS "\s-1MC\s0 Coordinates" .IX Subsection "MC Coordinates" Option \f(CW\*(C`coordinates => \*(AqMC\*(Aq\*(C'\fR gives the medium leg and hypotenuse from each triple, .PP .Vb 1 \& coordinates => "MC" \& \& 65 | 11 40 \& 61 | 41 \& | \& 53 | 7 \& | \& | \& 41 | 14 \& 37 | 13 \& | \& 29 | 3 \& 25 | 5 \& | \& 17 | 4 \& 13 | 2 \& | \& Y=5 | 1 \& | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=4 15 24 35 40 56 63 .Ve .PP The points are in a wedge 0.7*Y < X < Y. X is the bigger leg and X^2\ >\ Y^2/2 so X\ >\ Y*1/\fIsqrt\fR\|(2). .SS "\s-1UAD\s0 Coordinates \s-1AB, AC, PQ\s0 \*(-- Turn Right" .IX Subsection "UAD Coordinates AB, AC, PQ Turn Right" In the \s-1UAD\s0 tree with coordinates \s-1AB, AC\s0 or \s-1PQ\s0 the path always turns to the right. For example in \s-1AB\s0 coordinates at N=2 the path turns to the right to go towards N=3. .PP .Vb 1 \& coordinates => "AB" \& \& 20 | 3 N X,Y \& | \-\- \-\-\-\-\-\- \& 12 | 2 1 3,4 \& | 2 5,12 \& | 3 21,20 \& 4 | 1 \& | turn towards the \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- right at N=2 \& 3 5 21 .Ve .PP This can be proved from the transformations applied to seven cases, a triplet U,A,D, then four crossing a gap within a level, then two wrapping around at the end of a level. The initial N=1,2,3 can be treated as a wrap-around from the end of depth=0 (the last case D to U,A). .PP .Vb 3 \& U triplet U,A,D \& A \& D \& \& U.D^k.A crossing A,D to U \& U.D^k.D across U\->A gap \& A.U^k.U k>=0 \& \& A.D^k.A crossing A,D to U \& A.D^k.D across A\->D gap \& D.U^k.U k>=0 \& \& U.D^k.D crossing D to U,A \& U.U^k.U across U\->A gap \& A.U^k.A k>=0 \& \& A.D^k.D crossing D to U,A \& A.U^k.U across A\->D gap \& D.U^k.A k>=0 \& \& D^k .A wraparound A,D to U \& D^k .D k>=0 \& U^(k+1).U \& \& D^k wraparound D to U,A \& U^k.U k>=0 \& U^k.A (k=0 is initial N=1,N=2,N=3 for none,U,A) .Ve .PP The powers U^k and D^k are an arbitrary number of descents U or D. In P,Q coordinates these powers are .PP .Vb 2 \& U^k P,Q \-> (k+1)*P\-k*Q, k*P\-(k\-1)*Q \& D^k P,Q \-> P+2k*Q, Q .Ve .PP For \s-1AC\s0 coordinates squaring to stretch to P^2,Q^2 doesn't change the turns. Then a rotate by \-45 degrees to A=P^2\-Q^2, C=P^2+Q^2 also doesn't change the turns. .SS "\s-1UAD\s0 Coordinates \s-1BC\s0 \*(-- Turn Left" .IX Subsection "UAD Coordinates BC Turn Left" In the \s-1UAD\s0 tree with coordinates \s-1BC\s0 the path always turns to the left. For example in \s-1BC\s0 coordinates at N=2 the path turns to the right to go towards N=3. .PP .Vb 1 \& coordinates => "BC" \& \& 29 | 3 N X,Y \& | \-\- \-\-\-\-\-\- \& | 1 4,5 \& | 2 12,13 \& 13 | 2 3 20,29 \& | \& 5 | 1 turn towards the \& | left at N=2 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& 4 12 20 .Ve .PP As per above A,C turns to the right, which squared is A^2,C^2 to the right too, which equals C^2\-B^2,C^2. Negating the X coordinate to B^2\-C^2,C^2 mirrors to be a left turn always, and addition shearing to X+Y,Y doesn't change that, giving B^2,C^2 always left and so B,C always left. .SH "FUNCTIONS" .IX Header "FUNCTIONS" See \*(L"\s-1FUNCTIONS\*(R"\s0 in Math::PlanePath for behaviour common to all path classes. .ie n .IP """$path = Math::PlanePath::PythagoreanTree\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::PythagoreanTree\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::PythagoreanTree->new ()" .PD 0 .ie n .IP """$path = Math::PlanePath::PythagoreanTree\->new (tree_type => $str, coordinates => $str)""" 4 .el .IP "\f(CW$path = Math::PlanePath::PythagoreanTree\->new (tree_type => $str, coordinates => $str)\fR" 4 .IX Item "$path = Math::PlanePath::PythagoreanTree->new (tree_type => $str, coordinates => $str)" .PD Create and return a new path object. The \f(CW\*(C`tree_type\*(C'\fR option can be .Sp .Vb 4 \& "UAD" (the default) \& "UArD" UAD with Gray code reflections \& "FB" \& "UMT" .Ve .Sp The \f(CW\*(C`coordinates\*(C'\fR option can be .Sp .Vb 7 \& "AB" odd, even legs (the default) \& "AC" odd leg, hypotenuse \& "BC" even leg, hypotenuse \& "PQ" \& "SM" small, medium legs \& "SC" small leg, hypotenuse \& "MC" medium leg, hypotenuse .Ve .Sp The \f(CW\*(C`digit_order\*(C'\fR option can be .Sp .Vb 2 \& "HtoL" high to low (the default) \& "LtoH" low to high (the default) .Ve .ie n .IP """$n = $path\->n_start()""" 4 .el .IP "\f(CW$n = $path\->n_start()\fR" 4 .IX Item "$n = $path->n_start()" Return 1, the first N in the path. .ie n .IP """($x,$y) = $path\->n_to_xy ($n)""" 4 .el .IP "\f(CW($x,$y) = $path\->n_to_xy ($n)\fR" 4 .IX Item "($x,$y) = $path->n_to_xy ($n)" Return the X,Y coordinates of point number \f(CW$n\fR on the path. Points begin at 1 and if \f(CW\*(C`$n<1\*(C'\fR then the return is an empty list. .ie n .IP """$n = $path\->xy_to_n ($x,$y)""" 4 .el .IP "\f(CW$n = $path\->xy_to_n ($x,$y)\fR" 4 .IX Item "$n = $path->xy_to_n ($x,$y)" Return the point number for coordinates \f(CW\*(C`$x,$y\*(C'\fR. If there's nothing at \&\f(CW\*(C`$x,$y\*(C'\fR then return \f(CW\*(C`undef\*(C'\fR. .Sp The return is \f(CW\*(C`undef\*(C'\fR if \f(CW\*(C`$x,$y\*(C'\fR is not a primitive Pythagorean triple, per the \f(CW\*(C`coordinates\*(C'\fR option. .ie n .IP """$rsquared = $path\->n_to_radius ($n)""" 4 .el .IP "\f(CW$rsquared = $path\->n_to_radius ($n)\fR" 4 .IX Item "$rsquared = $path->n_to_radius ($n)" Return the radial distance R=sqrt(X^2+Y^2) of point \f(CW$n\fR. If there's no point \f(CW$n\fR then return \f(CW\*(C`undef\*(C'\fR. .Sp For coordinates=AB or \s-1SM\s0 this is the hypotenuse C and therefore an integer, for integer \f(CW$n\fR. .ie n .IP """($n_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)""" 4 .el .IP "\f(CW($n_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)\fR" 4 .IX Item "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)" Return a range of N values which occur in a rectangle with corners at \&\f(CW$x1\fR,\f(CW$y1\fR and \f(CW$x2\fR,\f(CW$y2\fR. The range is inclusive. .Sp Both trees go off into large X,Y coordinates while yet to finish values close to the origin which means the N range for a rectangle can be quite large. For \s-1UAD \s0\f(CW$n_hi\fR is roughly \f(CW\*(C`3**max(x/2)\*(C'\fR, or for \s-1FB\s0 smaller at roughly \f(CW\*(C`3**log2(x)\*(C'\fR. .SS "Descriptive Methods" .IX Subsection "Descriptive Methods" .ie n .IP """$x = $path\->x_minimum()""" 4 .el .IP "\f(CW$x = $path\->x_minimum()\fR" 4 .IX Item "$x = $path->x_minimum()" .PD 0 .ie n .IP """$y = $path\->y_minimum()""" 4 .el .IP "\f(CW$y = $path\->y_minimum()\fR" 4 .IX Item "$y = $path->y_minimum()" .PD Return the minimum X or Y occurring in the path. The value goes according to the \f(CW\*(C`coordinates\*(C'\fR option, .Sp .Vb 7 \& coordinate minimum \& \-\-\-\-\-\-\-\-\-\- \-\-\-\-\-\-\- \& A,S 3 \& B,M 4 \& C 5 \& P 2 \& Q 1 .Ve .SS "Tree Methods" .IX Subsection "Tree Methods" Each point has 3 children, so the path is a complete ternary tree. .IX Xref "Complete ternary tree" .ie n .IP """@n_children = $path\->tree_n_children($n)""" 4 .el .IP "\f(CW@n_children = $path\->tree_n_children($n)\fR" 4 .IX Item "@n_children = $path->tree_n_children($n)" Return the three children of \f(CW$n\fR, or an empty list if \f(CW\*(C`$n < 1\*(C'\fR (ie. before the start of the path). .Sp This is simply \f(CW\*(C`3*$n\-1, 3*$n, 3*$n+1\*(C'\fR. This is appending an extra ternary digit 0, 1 or 2 to the mixed-radix form for N described above. Or staying all in ternary then appending to N+1 rather than N and adjusting back. .ie n .IP """$num = $path\->tree_n_num_children($n)""" 4 .el .IP "\f(CW$num = $path\->tree_n_num_children($n)\fR" 4 .IX Item "$num = $path->tree_n_num_children($n)" Return 3, since every node has three children, or return \f(CW\*(C`undef\*(C'\fR if \&\f(CW\*(C`$n<1\*(C'\fR (ie. before the start of the path). .ie n .IP """$n_parent = $path\->tree_n_parent($n)""" 4 .el .IP "\f(CW$n_parent = $path\->tree_n_parent($n)\fR" 4 .IX Item "$n_parent = $path->tree_n_parent($n)" Return the parent node of \f(CW$n\fR, or \f(CW\*(C`undef\*(C'\fR if \f(CW\*(C`$n <= 1\*(C'\fR (the top of the tree). .Sp This is simply \f(CW\*(C`floor(($n+1)/3)\*(C'\fR, reversing the \f(CW\*(C`tree_n_children()\*(C'\fR calculation above. .ie n .IP """$depth = $path\->tree_n_to_depth($n)""" 4 .el .IP "\f(CW$depth = $path\->tree_n_to_depth($n)\fR" 4 .IX Item "$depth = $path->tree_n_to_depth($n)" Return the depth of node \f(CW$n\fR, or \f(CW\*(C`undef\*(C'\fR if there's no point \f(CW$n\fR. The top of the tree at N=1 is depth=0, then its children depth=1, etc. .Sp The structure of the tree with 3 nodes per point means the depth is floor(log3(2N\-1)), so for example N=5 through N=13 all have depth=2. .ie n .IP """$n = $path\->tree_depth_to_n($depth)""" 4 .el .IP "\f(CW$n = $path\->tree_depth_to_n($depth)\fR" 4 .IX Item "$n = $path->tree_depth_to_n($depth)" .PD 0 .ie n .IP """$n = $path\->tree_depth_to_n_end($depth)""" 4 .el .IP "\f(CW$n = $path\->tree_depth_to_n_end($depth)\fR" 4 .IX Item "$n = $path->tree_depth_to_n_end($depth)" .PD Return the first or last N at tree level \f(CW$depth\fR in the path, or \f(CW\*(C`undef\*(C'\fR if nothing at that depth or not a tree. The top of the tree is depth=0. .SS "Tree Descriptive Methods" .IX Subsection "Tree Descriptive Methods" .ie n .IP """$num = $path\->tree_num_children_minimum()""" 4 .el .IP "\f(CW$num = $path\->tree_num_children_minimum()\fR" 4 .IX Item "$num = $path->tree_num_children_minimum()" .PD 0 .ie n .IP """$num = $path\->tree_num_children_maximum()""" 4 .el .IP "\f(CW$num = $path\->tree_num_children_maximum()\fR" 4 .IX Item "$num = $path->tree_num_children_maximum()" .PD Return 3 since every node has 3 children, making that both the minimum and maximum. .ie n .IP """$bool = $path\->tree_any_leaf()""" 4 .el .IP "\f(CW$bool = $path\->tree_any_leaf()\fR" 4 .IX Item "$bool = $path->tree_any_leaf()" Return false, since there are no leaf nodes in the tree. .SH "FORMULAS" .IX Header "FORMULAS" .SS "\s-1UAD\s0 Matrices" .IX Subsection "UAD Matrices" Internally the code uses P,Q and calculates A,B at the end as necessary. The \s-1UAD\s0 transformations in P,Q coordinates are .PP .Vb 2 \& U P \-> 2P\-Q ( 2 \-1 ) \& Q \-> P ( 1 0 ) \& \& A P \-> 2P+Q ( 2 1 ) \& Q \-> P ( 1 0 ) \& \& D P \-> P+2Q ( 1 2 ) \& Q \-> Q unchanged ( 0 1 ) .Ve .PP The advantage of P,Q for the calculation is that it's 2 values instead of 3. The transformations can be written with the 2x2 matrices shown, but explicit steps are enough for the code. .PP Repeatedly applying \*(L"U\*(R" gives .PP .Vb 6 \& U 2P\-Q, P \& U^2 3P\-2Q, 2P\-Q \& U^3 4P\-3Q, 3P\-2Q \& ... \& U^k (k+1)P\-kQ, kP\-(k\-1)Q \& = P+k(P\-Q), Q+k*(P\-Q) .Ve .PP If there's a run of k many high zeros in the Nrem = N\-Nrow position in the level then they can be applied to the initial P=2,Q=1 as .PP .Vb 1 \& U^k P=k+2, Q=k+1 start for k high zeros .Ve .SS "\s-1FB\s0 Transformations" .IX Subsection "FB Transformations" The \s-1FB\s0 tree is calculated in P,Q and converted to A,B at the end as necessary. Its three transformations are .PP .Vb 2 \& M1 P \-> P+Q ( 1 1 ) \& Q \-> 2Q ( 0 2 ) \& \& M2 P \-> 2P ( 2 0 ) \& Q \-> P\-Q ( 1 \-1 ) \& \& M3 P \-> 2P ( 2 0 ) \& Q \-> P+Q ( 1 1 ) .Ve .PP Price's paper shows rearrangements of a set of four values q',q,p,p'. Just the p and q are enough for the calculation. The set of four has some attractive geometric interpretations though. .SS "X,Y to N \*(-- \s-1UAD\s0" .IX Subsection "X,Y to N UAD" \&\f(CW\*(C`xy_to_n()\*(C'\fR works in P,Q coordinates. An A,B or other input is converted to P,Q per the formulas in \*(L"\s-1PQ\s0 Coordinates\*(R" above. A P,Q point can be reversed up the \s-1UAD\s0 tree to its parent point .PP .Vb 2 \& if P > 3Q reverse "D" P \-> P\-2Q \& digit=2 Q \-> unchanged \& \& if P > 2Q reverse "A" P \-> Q \& digit=1 Q \-> P\-2Q \& \& otherwise reverse "U" P \-> Q \& digit=0 Q \-> 2Q\-P .Ve .PP This gives a ternary digit 2, 1, 0 respectively from low to high. Those plus a high \*(L"1\*(R" bit make N. The number of steps is the \*(L"depth\*(R" level. .PP If at any stage P,Q doesn't satisfy P>Q>=1, one odd, the other even, then it means the original point, however it was converted, was not a primitive triple. For a primitive triple the endpoint is always P=2,Q=1. .PP The conditions P>3Q or P>2Q work because each matrix sends its parent P,Q to one of three disjoint regions, .PP .Vb 10 \& Q P=Q P=2Q P=3Q \& | * U \-\-\-\- A ++++++ \& | * \-\-\-\- ++++++ \& | * \-\-\-\- ++++++ \& | * \-\-\-\- ++++++ \& | * \-\-\-\- ++++++ \& | * \-\-\-\- ++++++ \& | * \-\-\-\- ++++++ D \& | * \-\-\-\-++++++ \& | * \-\-\-\-++++ \& | \-\-\-\-++ \& | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- P .Ve .PP So U is the upper wedge, A the middle, and D the lower. The parent P,Q can be anywhere in P>Q>=1, the matrices always map to these regions. .SS "X,Y to N \*(-- \s-1FB\s0" .IX Subsection "X,Y to N FB" After converting to P,Q as necessary, a P,Q point can be reversed up the \s-1FB\s0 tree to its parent .PP .Vb 2 \& if P odd reverse M1 P \-> P\-Q \& (Q even) Q \-> Q/2 \& \& if P > 2Q reverse M2 P \-> P/2 \& (P even) Q \-> P/2 \- Q \& \& otherwise reverse M3 P \-> P/2 \& (P even) Q \-> Q \- P/2 .Ve .PP This is a little like the binary greatest common divisor algorithm, but designed for one value odd and the other even. Like the \s-1UAD\s0 ascent above if at any stage P,Q doesn't satisfy P>Q>=1, one odd, the other even, then the initial point wasn't a primitive triple. .PP The M1 reversal works because M1 sends any parent P,Q to a child which has P odd. All odd P,Q comes from M1. The M2 and M3 always make children with P even. Those children are divided between two disjoint regions above and below the line P=2Q. .PP .Vb 10 \& Q P=Q P=2Q \& | * M3 P=even \-\-\-\- \& | * \-\-\-\- \& | * \-\-\-\- \& | * \-\-\-\- \& | * \-\-\-\- M2 P=even \& | * \-\-\-\- \& | * \-\-\-\- \& | * \-\-\-\- \& | * \-\-\-\- M1 P=odd anywhere \& | \-\-\-\- \& | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- P .Ve .SS "X,Y to N \*(-- \s-1UMT\s0" .IX Subsection "X,Y to N UMT" After converting to P,Q as necessary, a P,Q point can be reversed up the \s-1UMT\s0 tree to its parent .PP .Vb 2 \& if P > 2Q reverse "U" P \-> Q \& digit=0 Q \-> 2Q\-P \& \& if P even reverse "M2" P \-> P/2 \& (Q odd) Q \-> P/2 \- Q \& \& otherwise reverse "T" P \-> P \- 3 * Q/2 \& (Q even) Q \-> Q/2 .Ve .PP These reversals work because U sends any parent P,Q to a child P>2Q whereas the M2 and T go below that line. M2 and T are distinguished by M2 giving P even whereas T gives P odd. .PP .Vb 10 \& Q P=Q P=2Q \& | * U \-\-\-\- \& | * \-\-\-\- \& | * \-\-\-\- \& | * \-\-\-\- \& | * \-\-\-\- M2 for P=even \& | * \-\-\-\- T for P=odd \& | * \-\-\-\- \& | * \-\-\-\- \& | * \-\-\-\- \& | \-\-\-\- \& | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- P .Ve .SS "Rectangle to N Range \*(-- \s-1UAD\s0" .IX Subsection "Rectangle to N Range UAD" For the \s-1UAD\s0 tree, the smallest A,B within each level is found at the topmost \&\*(L"U\*(R" steps for the smallest A or the bottom-most \*(L"D\*(R" steps for the smallest B. For example in the table above of level=2 N=5..13 the smallest A is the top A=7,B=24, and the smallest B is in the bottom A=35,B=12. In general .PP .Vb 2 \& Amin = 2*level + 1 \& Bmin = 4*level .Ve .PP In P,Q coordinates the same topmost line is the smallest P and bottom-most the smallest Q. The values are .PP .Vb 2 \& Pmin = level+1 \& Qmin = 1 .Ve .PP The fixed Q=1 arises from the way the \*(L"D\*(R" transformation sends Q\->Q unchanged, so every level includes a Q=1. This means if you ask what range of N is needed to cover all Q < someQ then there isn't one, only a P < someP has an N to go up to. .SS "Rectangle to N Range \*(-- \s-1FB\s0" .IX Subsection "Rectangle to N Range FB" For the \s-1FB\s0 tree, the smallest A,B within each level is found in the topmost two final positions. For example in the table above of level=2 N=5..13 the smallest A is in the top A=9,B=40, and the smallest B is in the next row A=35,B=12. In general, .PP .Vb 2 \& Amin = 2^level + 1 \& Bmin = 2^level + 4 .Ve .PP In P,Q coordinates a Q=1 is found in that second row which is the minimum B, and the smallest P is found by taking M1 steps half-way then a M2 step, then M1 steps for the balance. This is a slightly complicated .PP .Vb 3 \& Pmin = / 3*2^(k\-1) + 1 if even level = 2*k \& \e 2^(k+1) + 1 if odd level = 2*k+1 \& Q = 1 .Ve .PP The fixed Q=1 arises from the M1 steps giving .PP .Vb 4 \& P = 2 + 1+2+4+8+...+2^(level\-2) \& = 2 + 2^(level\-1) \- 1 \& = 2^(level\-1) + 1 \& Q = 2^(level\-1) \& \& followed by M2 step \& Q \-> P\-Q \& = 1 .Ve .PP As for the \s-1UAD\s0 above this means small Q's always remain no matter how big N gets, only a P range determines an N range. .SH "OEIS" .IX Header "OEIS" Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include, .Sp .RS 4 (etc) .RE .PP .Vb 3 \& A007051 N start of depth=n, (3^n+1)/2, ie. tree_depth_to_n() \& A003462 N end of depth=n\-1, (3^n\-1)/2, ie. tree_depth_to_n_end() \& A000244 N of row middle line, 3^n \& \& A058529 possible values taken by abs(A\-B), \& being integers with all prime factors == +/\-1 mod 8 \& \& "U" repeatedly \& A046092 coordinate B, 2n(n+1) = 4*triangular numbers \& A099776 \e coordinate C, being 2n(n+1)+1 \& A001844 / which is the "centred squares" \& \& "A" repeatedly \& A046727 \e coordinate A \& A084159 / "Pell oblongs" \& A046729 coordinate B \& A001653 coordinate C, numbers n where 2*n^2\-1 is square \& A000129 coordinate P and Q, the Pell numbers \& A001652 coordinate S, the smaller leg \& A046090 coordinate M, the bigger leg \& \& "D" repeatedly \& A000466 coordinate A, being 4*n^2\-1 for n>=1 \& \& "M1" repeatedly \& A028403 coordinate B, binary 10..010..000 \& A007582 coordinate B/4, binary 10..010..0 \& A085601 coordinate C, binary 10..010..001 \& \& "M2" repeatedly \& A015249 \e coordinate A, binary 111000111000... \& A084152 | \& A084175 / \& A054881 coordinate B, binary 1010..1010000..00 \& \& "M3" repeatedly \& A106624 coordinate P,Q pairs, 2^k\-1,2^k \& \& "T" repeatedly \& A134057 coordinate A, binomial(2^n\-1,2) \& binary 111..11101000..0001 \& A093357 coordinate B, binary 10111..111000..000 \& A052940 \e \& A055010 | coordinate P, 3*2^n\-1 \& A083329 | binary 10111..111 \& A153893 / .Ve .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::Hypot, Math::PlanePath::RationalsTree, Math::PlanePath::CoprimeColumns .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2011, 2012, 2013, 2014 Kevin Ryde .PP This file is part of Math-PlanePath. .PP Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the \s-1GNU\s0 General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. .PP Math-PlanePath is distributed in the hope that it will be useful, but \&\s-1WITHOUT ANY WARRANTY\s0; without even the implied warranty of \s-1MERCHANTABILITY\s0 or \s-1FITNESS FOR A PARTICULAR PURPOSE. \s0 See the \s-1GNU\s0 General Public License for more details. .PP You should have received a copy of the \s-1GNU\s0 General Public License along with Math-PlanePath. If not, see .