.\" Automatically generated by Pod::Man 4.14 (Pod::Simple 3.40) .\" .\" 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 >0, 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 .\" ======================================================================== .\" .IX Title "Math::PlanePath::ChanTree 3pm" .TH Math::PlanePath::ChanTree 3pm "2021-01-23" "perl v5.32.0" "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::ChanTree \-\- tree of rationals .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::ChanTree; \& my $path = Math::PlanePath::ChanTree\->new (k => 3, reduced => 0); \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This path enumerates rationals X/Y in a tree as per .IX Xref "Chan, Song Heng" .Sp .RS 4 Song Heng Chan, \*(L"Analogs of the Stern Sequence\*(R", Integers 2011, .RE .PP The default k=3 visits X,Y with one odd, one even, and perhaps a common factor 3^m. .PP .Vb 10 \& 14 | 728 20 12 \& 13 | 53 11 77 27 \& 12 | 242 14 18 \& 11 | \& 10 | 80 \& 9 | 17 23 9 15 \& 8 | 26 78 \& 7 | \& 6 | 8 24 28 \& 5 | 5 3 19 \& 4 | 2 6 10 22 \& 3 | \& 2 | 0 4 16 52 \& 1 | 1 7 25 79 241 727 \& Y=0 | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 .Ve .PP There are 2 tree roots (so technically it's a \*(L"forest\*(R") and each node has 3 children. The points are numbered by rows starting from N=0. This numbering corresponds to powers in a polynomial product generating function. .PP .Vb 5 \& N=0 to 1 1/2 2/1 \& / | \e / | \e \& N=2 to 7 1/4 4/5 5/2 2/5 5/4 4/1 \& / | \e ... ... ... ... / | \e \& N=8 to 25 1/6 6/9 9/4 ... ... 5/9 9/6 6/1 \& \& N=26 ... .Ve .PP The children of each node are .PP .Vb 4 \& X/Y \& \-\-\-\-\-\-\-\-\-\-\-\-/ | \e\-\-\-\-\-\-\-\-\-\-\- \& | | | \& X/(2X+Y) (2X+Y)/(X+2Y) (X+2Y)/Y .Ve .PP Which as X,Y coordinates means vertical, 45\-degree diagonal, and horizontal. .PP .Vb 6 \& X,Y+2X X+(X+Y),Y+(X+Y) \& | / \& | / \& | / \& | / \& X,Y\-\-\-\-\-\-\- X+2Y,Y .Ve .PP The slowest growth is on the far left of the tree 1/2, 1/4, 1/6, 1/8, etc advancing by just 2 at each level. Similarly on the far right 2/1, 4/1, 6/1, etc. This means that to cover such an X or Y requires a power\-of\-3, N=3^(max(X,Y)/2). .SS "\s-1GCD\s0" .IX Subsection "GCD" Chan shows that these top nodes and children visit all rationals X/Y with X,Y one odd, one even. But the X,Y are not in least terms, they may have a power\-of\-3 common factor \s-1GCD\s0(X,Y)=3^m for some m. .PP The \s-1GCD\s0 is unchanged in the first and third children. The middle child \s-1GCD\s0 might gain an extra factor 3. This means the power is at most the number of middle legs taken, which is the count of ternary 1\-digits of its position across the row. .PP .Vb 2 \& GCD(X,Y) = 3^m \& m <= count ternary 1\-digits of N+1, excluding high digit .Ve .PP As per \*(L"N Start\*(R" below, N+1 in ternary has high digit 1 or 2 which indicates the tree root. Ignoring that high digit gives an offset into the row of that tree and the digits are 0,1,2 for left,middle,right. .PP For example the first \s-1GCD\s0 is at N=9 with X=6,Y=9 common factor GCD=3. N+1=10=\*(L"101\*(R" ternary, which without the high digit is \*(L"01\*(R" which has a single \*(L"1\*(R" so \s-1GCD\s0 <= 3^1. The mirror image of this point is X=9,Y=6 at N=24 and there N+1=24+1=25=\*(L"221\*(R" ternary which without the high digit is \*(L"21\*(R" with a single 1\-digit likewise. .PP For various points the power m is equal to the count of 1\-digits. .SS "k Parameter" .IX Subsection "k Parameter" Parameter \f(CW\*(C`k => $integer\*(C'\fR controls the number of children and top nodes. There are k\-1 top nodes and each node has k children. The top nodes are .PP .Vb 2 \& k odd, k\-1 many tops, with h=ceil(k/2) \& 1/2 2/3 3/4 ... (h\-1)/h h/(h\-1) ... 4/3 3/2 2/1 \& \& k even, k\-1 many tops, with h=k/2 \& 1/2 2/3 3/4 ... (h\-1)/h h/h h/(h\-1) ... 4/3 3/2 2/1 .Ve .PP Notice the list for k odd or k even is the same except that for k even there's an extra middle term h/h. The first few tops are as follows. The list in each row is spread to show how successive bigger h adds terms in the middle. .PP .Vb 3 \& k X/Y top nodes \& \-\-\- \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& k=2 1/1 \& \& k=3 1/2 2/1 \& k=4 1/2 2/2 2/1 \& \& k=5 1/2 2/3 3/2 2/1 \& k=6 1/2 2/3 3/3 3/2 2/1 \& \& k=7 1/2 2/3 3/4 4/3 3/2 2/1 \& k=8 1/2 2/3 3/4 4/4 4/3 3/2 2/1 .Ve .PP As X,Y coordinates these tops are a run up along X=Y\-1 and back down along X=Y+1, with a middle X=Y point if k even. For example, .PP .Vb 10 \& 7 | 5 k=13 top nodes N=0 to N=11 \& 6 | 4 6 total 12 top nodes \& 5 | 3 7 \& 4 | 2 8 \& 3 | 1 9 \& 2 | 0 10 \& 1 | 11 \& Y=0 | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 \& \& k=14 top nodes N=0 to N=12 \& 7 | 5 6 total 13 top nodes \& 6 | 4 7 \& 5 | 3 8 N=6 is the 7/7 middle term \& 4 | 2 9 \& 3 | 1 10 \& 2 | 0 11 \& 1 | 12 \& Y=0 | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 .Ve .PP Each node has k children. The formulas for the children can be seen from sample cases k=5 and k=6. A node X/Y descends to .PP .Vb 1 \& k=5 k=6 \& \& 1X+0Y / 2X+1Y 1X+0Y / 2X+1Y \& 2X+1Y / 3X+2Y 2X+1Y / 3X+2Y \& 3X+2Y / 2X+3Y 3X+2Y / 3X+3Y \& 2X+3Y / 1X+2Y 3X+3Y / 2X+3Y \& 1X+2Y / 0X+1Y 2X+3Y / 1X+2Y \& 1X+2Y / 0X+1Y .Ve .PP The coefficients of X and Y run up to h=ceil(k/2) starting from either 0, 1 or 2 and ending 2, 1 or 0. When k is even there's two h coeffs in the middle. When k is odd there's just one. The resulting tree for example with k=4 is .PP .Vb 4 \& k=4 \& 1/2 2/2 2/1 \& / \e / \e / \e \& 1/4 4/6 6/5 5/2 2/6 6/8 8/6 6/2 2/5 5/6 6/4 4/1 .Ve .PP Chan shows that this combination of top nodes and children visits .PP .Vb 2 \& if k odd: rationals X/Y with X,Y one odd, one even \& possible GCD(X,Y)=k^m for some integer m \& \& if k even: all rationals X/Y \& possible GCD(X,Y) a divisor of (k/2)^m .Ve .PP When k odd, \s-1GCD\s0(X,Y) is a power of k, so for example as described above k=3 gives GCD=3^m. When k even \s-1GCD\s0(X,Y) is a divisor of (k/2)^m but not necessarily a full such power. For example with k=12 the first such non-power \s-1GCD\s0 is at N=17 where X=16,Y=18 has \s-1GCD\s0(16,18)=2 which is only a divisor of k/2=6, not a power of 6. .SS "N Start" .IX Subsection "N Start" The \f(CW\*(C`n_start => $n\*(C'\fR option can select a different initial N. The tree structure is unchanged, just the numbering shifted. As noted above the default Nstart=0 corresponds to powers in a generating function. .PP \&\f(CW\*(C`n_start=>1\*(C'\fR makes the numbering correspond to digits of N written in base-k. For example k=10 corresponds to N written in decimal, .PP .Vb 1 \& N=1 to 9 1/2 ... ... 2/1 \& \& N=10 to 99 1/4 4/7 ... ... 7/4 4/1 \& \& N=100 to 999 1/6 6/11 ... ... 11/6 6/1 .Ve .PP In general \f(CW\*(C`n_start=>1\*(C'\fR makes the tree .PP .Vb 5 \& N written in base\-k digits \& depth = numdigits(N)\-1 \& NdepthStart = k^depth \& = 100..000 base\-k, high 1 in high digit position of N \& N\-NdepthStart = position across whole row of all top trees .Ve .PP And the high digit of N selects which top-level tree the given N is under, so .PP .Vb 7 \& N written in base\-k digits \& top tree = high digit of N \& (1 to k, selecting the k\-1 many top nodes) \& Nrem = digits of N after the highest \& = position across row within the high\-digit tree \& depth = numdigits(Nrem) # top node depth=0 \& = numdigits(N)\-1 .Ve .SS "Diatomic Sequence" .IX Subsection "Diatomic Sequence" Chan shows that each denominator Y becomes the numerator X in the next point. The last Y of a row becomes the first X of the next row. This is a generalization of Stern's diatomic sequence and of the Calkin-Wilf tree of rationals. (See Math::NumSeq::SternDiatomic and \&\*(L"Calkin-Wilf Tree\*(R" in Math::PlanePath::RationalsTree.) .PP The case k=2 is precisely the Calkin-Wilf tree. There's just one top node 1/1, being the even k \*(L"middle\*(R" form h/h with h=k/2=1 as described above. Then there's two children of each node (the \*(L"middle\*(R" pair of the even k case), .PP .Vb 1 \& k=2, Calkin\-Wilf tree \& \& X/Y \& / \e \& (1X+0Y)/(1X+1Y) (1X+1Y)/(0X+1Y) \& = X/(X+Y) = (X+Y)/Y .Ve .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::ChanTree\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::ChanTree\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::ChanTree->new ()" .PD 0 .ie n .IP """$path = Math::PlanePath::ChanTree\->new (k => $k, n_start => $n)""" 4 .el .IP "\f(CW$path = Math::PlanePath::ChanTree\->new (k => $k, n_start => $n)\fR" 4 .IX Item "$path = Math::PlanePath::ChanTree->new (k => $k, n_start => $n)" .PD Create and return a new path object. The defaults are k=3 and n_start=0. .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 the first N in the path. This is 0 by default, otherwise the \&\f(CW\*(C`n_start\*(C'\fR parameter. .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. .SS "Tree Methods" .IX Subsection "Tree Methods" Each point has k children, so the path is a complete k\-ary tree. .IX Xref "Complete n-ary 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 children of \f(CW$n\fR, or an empty list if \f(CW\*(C`$n < n_start()\*(C'\fR, ie. before the start of the path. .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 k, since every node has k children. Or return \f(CW\*(C`undef\*(C'\fR if \f(CW\*(C`$n < n_start()\*(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$n\fR has no parent either because it's a top node or before \f(CW\*(C`n_start()\*(C'\fR. .ie n .IP """$n_root = $path\->tree_n_root ($n)""" 4 .el .IP "\f(CW$n_root = $path\->tree_n_root ($n)\fR" 4 .IX Item "$n_root = $path->tree_n_root ($n)" Return the N which is root node of \f(CW$n\fR. .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 tree tops are depth=0, then their children depth=1, etc. .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. The top of the tree is depth=0. .SS "Tree Descriptive Methods" .IX Subsection "Tree Descriptive Methods" .ie n .IP """$num = $path\->tree_num_roots ()""" 4 .el .IP "\f(CW$num = $path\->tree_num_roots ()\fR" 4 .IX Item "$num = $path->tree_num_roots ()" Return the number of root nodes in \f(CW$path\fR, which is k\-1. For example the default k=3 return 2 as there are two root nodes. .ie n .IP """@n_list = $path\->tree_root_n_list ()""" 4 .el .IP "\f(CW@n_list = $path\->tree_root_n_list ()\fR" 4 .IX Item "@n_list = $path->tree_root_n_list ()" Return a list of the N values which are the root nodes of \f(CW$path\fR. This is \&\f(CW\*(C`n_start()\*(C'\fR through \f(CW\*(C`n_start()+k\-2\*(C'\fR inclusive, being the first k\-1 many points. For example in the default k=2 and Nstart=0 the return is two values \f(CW\*(C`(0,1)\*(C'\fR. .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 k since every node has k many 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 "N Children" .IX Subsection "N Children" For the default k=3 the children are .PP .Vb 1 \& 3N+2, 3N+3, 3N+4 n_start=0 .Ve .PP If \f(CW\*(C`n_start=>1\*(C'\fR then instead .PP .Vb 1 \& 3N, 3N+1, 3N+2 n_start=1 .Ve .PP For this \f(CW\*(C`n_start=1\*(C'\fR the children are found by appending an extra ternary digit, or base-k digit for arbitrary k. .PP .Vb 1 \& k*N, k*N+1, ... , k*N+(k\-1) n_start=1 .Ve .PP In general for k and Nstart the children are .PP .Vb 3 \& kN \- (k\-1)*(Nstart\-1) + 0 \& ... \& kN \- (k\-1)*(Nstart\-1) + k\-1 .Ve .SS "N Parent" .IX Subsection "N Parent" The parent node reverses the children calculation above. The simplest case is \f(CW\*(C`n_start=1\*(C'\fR where it's a division to remove the lowest base-k digit .PP .Vb 1 \& parent = floor(N/k) when n_start=1 .Ve .PP For other \f(CW\*(C`n_start\*(C'\fR adjust before and after to an \f(CW\*(C`n_start=1\*(C'\fR basis, .PP .Vb 1 \& parent = floor((N\-(Nstart\-1)) / k) + Nstart\-1 .Ve .PP For example in the default k=0 Nstart=1 the parent of N=3 is floor((3\-(1\-1))/3)=1. .PP The post-adjustment can be worked into the formula with (k\-1)*(Nstart\-1) similar to the children above, .PP .Vb 1 \& parent = floor((N + (k\-1)*(Nstart\-1)) / k) .Ve .PP But the first style is more convenient to compare to see that N is past the top nodes and therefore has a parent. .PP .Vb 1 \& N\-(Nstart\-1) >= k to check N is past top\-nodes .Ve .SS "N Root" .IX Subsection "N Root" As described under \*(L"N Start\*(R" above, if Nstart=1 then the tree root is simply the most significant base-k digit of N. For other Nstart an adjustment is made to N=1 style and back again. .PP .Vb 2 \& adjust = Nstart\-1 \& Nroot(N) = high_base_k_digit(N\-adjust) + adjust .Ve .SS "N to Depth" .IX Subsection "N to Depth" The structure of the tree means .PP .Vb 1 \& depth = floor(logk(N+1)) for n_start=0 .Ve .PP For example if k=3 then all of N=8 through N=25 inclusive have depth=floor(log3(N+1))=2. With an \f(CW\*(C`n_start\*(C'\fR it becomes .PP .Vb 1 \& depth = floor(logk(N\-(Nstart\-1))) .Ve .PP \&\f(CW\*(C`n_start=1\*(C'\fR is the simplest case, being the length of N written in base-k digits. .PP .Vb 1 \& depth = floor(logk(N)) for n_start=1 .Ve .SH "OEIS" .IX Header "OEIS" This tree is in Sloane's Online Encyclopedia of Integer Sequences as .Sp .RS 4 (etc) .RE .PP .Vb 2 \& k=3, n_start=0 (the defaults) \& A191379 X coordinate, and Y=X(N+n) .Ve .PP As noted above k=2 is the Calkin-Wilf tree. See \&\*(L"\s-1OEIS\*(R"\s0 in Math::PlanePath::RationalsTree for \*(L"\s-1CW\*(R"\s0 related sequences. .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::RationalsTree, Math::PlanePath::PythagoreanTree .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 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 .