NAME
Math::PlanePath::ChanTree -- tree of rationals
SYNOPSIS
use Math::PlanePath::ChanTree;
my $path = Math::PlanePath::ChanTree->new (k => 3, reduced => 0);
my ($x, $y) = $path->n_to_xy (123);DESCRIPTION
This path enumerates rationals X/Y in a tree by Song Heng Chan.
"Analogs of the Stern Sequence", Integers 2011
http://www.integers-ejcnt.org/l26/l26.pdfThe default k=3 visits X,Y with one odd one even and perhaps with a common factor 3^m.
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 13The tree has 2 roots (so technically it's a "forest") and 3 children under each node. The points are numbered by rows starting from N=0. (This numbering corresponds to powers in a polynomial product generating function.)
N=0 to 1 1/2 2/1
/ | \ / | \
N=2 to 7 1/4 4/5 5/2 2/5 5/4 4/1
/ | \ ... ... ... ... / | \
N=8 to 25 1/6 6/9 9/4 ... ... 5/9 9/6 6/1
N=26 ...The children of each node are
X/Y
------------/ | \-----------
| | |
X/(2X+Y) (2X+Y)/(X+2Y) (X+2Y)/YChan shows that these two top nodes and children visit all rationals X/Y with X,Y one odd one even. X,Y are not in least terms, they may have a power-of-3 common factor GCD(X,Y)=3^m for some integer m. The first such factor for example is at N=10 where X=6,Y=9 representing 2/3 has common factor 3.
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, and similarly on the far right inverses 2/1, 4/1, 6/1, etc. This means that to cover such an X or Y requires N growing as a power of 3, N=3^(max(X,Y)/2).
k Parameter
The k => $integer parameter controls the number of top nodes and children. There are k-1 top nodes and each node has k children. The top nodes are
k odd, k-1 even tops, 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 odd tops, h=k/2
1/2 2/3 3/4 ... (h-1)/h h/h h/(h-1) ... 4/3 3/2 2/1So,
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/1There are k children of each node. The formulas for the children can be seen from sample cases k=5 and k=6.
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+1YThe 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 k=4 is
k=4
1/2 2/2 2/1
/ \ / \ / \
1/4 4/6 6/5 5/2 2/6 6/8 8/6 6/2 2/5 5/6 6/4 4/1Chan shows that this combination of top nodes and children visits
if k odd rationals X,Y with one odd one even
possible GCD(X,Y)=k^m for some m
if k even all rationals
possible GCD(X,Y) dividing (k/2)^m for some mWhen k odd GCD(X,Y) is a power of k, as noted above for instance k=3 is a power-of-3. When k even GCD(X,Y) is a divisor of (k/2)^m, but not necessarily a whole such power. For example in k=12 the first such non-power GCD is at N=17 where X=16,Y=18 has GCD(16,18)=2 which is only a divisor of k/2=6, not a whole power.
N Start
The n_start => $n option can select a different initial N. The tree structure is unchanged, just the numbering offset.
n_start=>1 makes the numbering correspond to digits of N written in base-k. The length of N in digits is the tree level, the high digit is which of the k-1 trees, and the further digits the position within the row. Or equivalently the position within the row across all trees is N-k^level, ie. counting from 100..000 in base-k. For example k=10 with N in decimal,
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/1Diatomic Sequence
Each denominator Y becomes the numerator X in the next point, including the last Y of a row becomeing 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 "Calkin-Wilf Tree" in Math::PlanePath::RationalsTree.
The case k=2 is the Calkin-Wilf tree. There's just one top node 1/1, being the even k "middle" form h/h for h=k/2=1 as described above. Then there's two children of each node, being the "middle" pair for even k,
X/Y k=2, Calkin-Wilf tree
/ \
(1X+0Y)/(1X+1Y) (1X+1Y)/(0X+1Y)
= X/(X+Y) = (X+Y)/YFUNCTIONS
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::ChanTree->new ()$path = Math::PlanePath::ChanTree->new (k => $k, n_start => $n)-
Create and return a new path object.
$n = $path->n_start()-
Return the first N in the path. This is N=0 by default, otherwise the
n_startparameter. $n = $path->xy_to_n ($x,$y)-
Return the point number for coordinates
$x,$y. If there's nothing at$x,$ythen returnundef.
Tree Methods
@n_children = $path->tree_n_children($n)-
Return the children of
$n, or an empty list if$n < n_start(), ie. before the start of the path. $num = $path->tree_n_num_children($n)-
Return k, since every node has k children. Or return
undefif$n < n_start(), ie. before the start of the path. $n_parent = $path->tree_n_parent($n)-
Return the parent node of
$n, orundefif$nhas no parent either because it's a top node or beforen_start(). $depth = $path->tree_n_to_depth($n)-
Return the depth of node
$n, orundefif there's no point$n. The tree tops are depth=0, then their children depth=1, etc. $n = $path->tree_depth_to_n($depth)$n = $path->tree_depth_to_n_end($depth)-
Return the first or last N at tree level
$depthin the path. The top of the tree is depth=0.
FORMULAS
Tree Children
For the default k=3 the children are
3N+2, 3N+3, 3N+4 n_start=0If n_start=>1 then it instead becomes like appending an extra ternary digit, or base-k digit, so
3N, 3N+1, 3N+2 n_start=1
k*K, k*N+1, ... , k*N+(k-1) n_start=1For a general k and Nstart the children are
kN - (k-1)*(Nstart-1) + 0
...
kN - (k-1)*(Nstart-1) + k-1Tree Parent
The parent node reverses the children calculation above. The simplest case is n_start=>1 where it's a division to remove the lowest base-k digit
parent = floor(N/k) when n_start=1And for other n_start then adjust before and after to an Nstart=1 basis,
parent = floor((N-Nstart+1) / k) + Nstart-1For example in the default k=0 Nstart=1 the parent of N=3 is floor((3-1+1)/3).
The post-adjustment can be worked into the formula with a (k-1)*(Nstart-1) similar to the children above, though the adjustment style above is more convenient when comparing N-Nstart+1 >= k to see that N is past the top nodes and therefore has a parent.
parent = floor((N + (k-1)*(Nstart-1)) / k)Tree Depth
The structure of the tree means
depth =floor(logk(N+1)) for n_start=0For example if k=3 then N=8 through N=25 all have depth=floor(log3(N+1))=2. With an n_start it adjusts to
depth = floor(logk(N+1-Nstart)).n_start=>1 is the simplest case, being the length of N written in base-k digits.
depth = floor(logk(N)) for n_start=1OEIS
This tree is in Sloane's Online Encyclopedia of Integer Sequences as
http://oeis.org/A191379 (etc)
n_start=0
A191379 X coordinateSEE ALSO
Math::PlanePath, Math::PlanePath::RationalsTree, Math::PlanePath::PythagoreanTree
HOME PAGE
http://user42.tuxfamily.org/math-planepath/index.html
LICENSE
Copyright 2012 Kevin Ryde
This file is part of Math-PlanePath.
Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
Math-PlanePath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.