Math::PlanePath::ChanTree -- tree of rationals
use Math::PlanePath::ChanTree; my $path = Math::PlanePath::ChanTree->new (k => 3, reduced => 0); my ($x, $y) = $path->n_to_xy (123);
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.pdf
The default k=3 visits X,Y with one odd one even and perhaps 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 13
The tree has 2 roots (so technically it's a "forest") and has 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)/Y
Chan shows that the two top nodes and these children visit all rationals X/Y with X,Y one odd one even. But X,Y are not in least terms, they may have a power-of-3 common factor GCD(X,Y)=3^m for integer m. The first such factor for example is at N=10 where X=6,Y=9 represents 2/3 but 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. 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).
The k => $integer parameter controls the number of children and top nodes. There are k-1 top nodes and each node has k children. The top nodes are
k => $integer
k odd, list of k-1 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, list of k-1 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
Notice the list for k odd or k even is the same except that when k even there's an extra middle term h/h. The first few k are as follows, spreading the list in each row to show how successive bigger h adds terms in the middle.
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
As X,Y coordinates these are a run up along X=Y-1 and back down along X=Y+1, with a middle X=Y if k even.
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
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
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
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
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/1
Chan shows that this combination of top nodes and children visits
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
When 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 full 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 full power of 6.
The n_start => $n 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.
n_start => $n
n_start=>1 makes the numbering correspond to digits of N written in base-k. For example k=10 with N in decimal,
n_start=>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
In general
N 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
And the high digit of N selects which top-level tree the given N is under, so
N 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
Each denominator Y becomes the numerator X in the next point, and 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 "Calkin-Wilf Tree" in Math::PlanePath::RationalsTree).
The case k=2 is in fact precisely the Calkin-Wilf tree. There's just one top node 1/1, being the even k "middle" form h/h with h=k/2=1 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)/Y
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_start parameter.
n_start
$n = $path->xy_to_n ($x,$y)
Return the point number for coordinates $x,$y. If there's nothing at $x,$y then return undef.
$x,$y
undef
Each point has k children, so the path is a complete k-ary tree.
@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.
$n
$n < n_start()
$num = $path->tree_n_num_children($n)
Return k, since every node has k children. Or return undef if $n < n_start(), ie. before the start of the path.
$n_parent = $path->tree_n_parent($n)
Return the parent node of $n, or undef if $n has no parent either because it's a top node or before n_start().
n_start()
$depth = $path->tree_n_to_depth($n)
Return the depth of node $n, or undef if 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 $depth in the path. The top of the tree is depth=0.
$depth
$num = $path->tree_num_children_minimum()
$num = $path->tree_num_children_maximum()
Return k since every node has k many children, making that both the minimum and maximum.
$bool = $path->tree_any_leaf()
Return false, since there are no leaf nodes in the tree.
For the default k=3 the children are
3N+2, 3N+3, 3N+4 n_start=0
If n_start=>1 then instead
3N, 3N+1, 3N+2 n_start=1
which is like appending an extra ternary digit, or base-k digit
k*N, k*N+1, ... , k*N+(k-1) n_start=1
In general for k and Nstart the children are
kN - (k-1)*(Nstart-1) + 0 ... kN - (k-1)*(Nstart-1) + k-1
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=1
For other n_start adjust before and after to an Nstart=1 basis,
parent = floor((N-Nstart+1) / k) + Nstart-1
For 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,
parent = floor((N + (k-1)*(Nstart-1)) / k)
The adjustment style is more convenient to compare to see that N is past the top nodes and therefore has a parent.
N-Nstart+1 >= k to check N is past top-nodes
The structure of the tree means
depth = floor(logk(N+1)) for n_start=0
For example if k=3 then N=8 through N=25 all have depth=floor(log3(N+1))=2. With an n_start it becomes
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=1
This tree is in Sloane's Online Encyclopedia of Integer Sequences as
http://oeis.org/A191379 (etc) k=3, n_start=0 (the defaults) A191379 X coordinate
As noted above, k=2 is the Calkin-Wilf tree. See "OEIS" in Math::PlanePath::RationalsTree for "CW" related sequences.
Math::PlanePath, Math::PlanePath::RationalsTree, Math::PlanePath::PythagoreanTree
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2012, 2013 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/>.
To install Math::PlanePath, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::PlanePath
CPAN shell
perl -MCPAN -e shell install Math::PlanePath
For more information on module installation, please visit the detailed CPAN module installation guide.