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.pdf

The 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  13

The 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)/Y

Chan 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/1

So,

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

There 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+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 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 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 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 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/1

Diatomic 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)/Y

FUNCTIONS

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 = $path->xy_to_n ($x,$y)

Return the point number for coordinates $x,$y. If there's nothing at $x,$y then return undef.

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 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().

$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.

FORMULAS

Tree Children

For the default k=3 the children are

3N+2, 3N+3, 3N+4        n_start=0

If 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=1

For a general k and Nstart the children are

kN - (k-1)*(Nstart-1)  + 0
 ...
kN - (k-1)*(Nstart-1)  + k-1

Tree 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=1

And for other n_start then 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, 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=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 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=1

OEIS

This tree is in Sloane's Online Encyclopedia of Integer Sequences as

http://oeis.org/A191379   (etc)

n_start=0
  A191379   X coordinate

SEE 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/>.