Math-PlanePath
view release on metacpan or search on metacpan
lib/Math/PlanePath/ChanTree.pm view on Meta::CPAN
nodes. There are k-1 top nodes and each node has k children. The top nodes
are
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
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.
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 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,
=cut
# math-image --path=ChanTree,k=13 --output=numbers --expression='i<12?i:0'
# math-image --path=ChanTree,k=14 --output=numbers --expression='i<13?i:0'
=pod
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, so for example as described above k=3
gives GCD=3^m. When k even GCD(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 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 power of 6.
=head2 N Start
The C<n_start =E<gt> $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.
C<n_start=E<gt>1> makes the numbering correspond to digits of N written in
base-k. For example k=10 corresponds to N written 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
In general C<n_start=E<gt>1> makes the tree
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
And the high digit of N selects which top-level tree the given N is under,
so
lib/Math/PlanePath/ChanTree.pm view on Meta::CPAN
default k=3 return 2 as there are two root nodes.
=item C<@n_list = $path-E<gt>tree_root_n_list ()>
Return a list of the N values which are the root nodes of C<$path>. This is
C<n_start()> through C<n_start()+k-2> inclusive, being the first k-1 many
points. For example in the default k=2 and Nstart=0 the return is two
values C<(0,1)>.
=item C<$num = $path-E<gt>tree_num_children_minimum()>
=item C<$num = $path-E<gt>tree_num_children_maximum()>
Return k since every node has k many children, making that both the minimum
and maximum.
=item C<$bool = $path-E<gt>tree_any_leaf()>
Return false, since there are no leaf nodes in the tree.
=back
=head1 FORMULAS
=head2 N Children
For the default k=3 the children are
3N+2, 3N+3, 3N+4 n_start=0
If C<n_start=E<gt>1> then instead
3N, 3N+1, 3N+2 n_start=1
For this C<n_start=1> the children are found by appending an extra ternary
digit, or base-k digit for arbitrary k.
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
=head2 N Parent
The parent node reverses the children calculation above. The simplest case
is C<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 C<n_start> adjust before and after to an C<n_start=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)=1.
The post-adjustment can be worked into the formula with (k-1)*(Nstart-1)
similar to the children above,
parent = floor((N + (k-1)*(Nstart-1)) / k)
But the first 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
=head2 N Root
As described under L</N Start> 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.
adjust = Nstart-1
Nroot(N) = high_base_k_digit(N-adjust) + adjust
=head2 N to Depth
The structure of the tree means
depth = floor(logk(N+1)) for n_start=0
For example if k=3 then all of N=8 through N=25 inclusive have
depth=floor(log3(N+1))=2. With an C<n_start> it becomes
depth = floor(logk(N-(Nstart-1)))
C<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
=head1 OEIS
This tree is in Sloane's Online Encyclopedia of Integer Sequences as
=over
L<http://oeis.org/A191379> (etc)
=back
k=3, n_start=0 (the defaults)
A191379 X coordinate, and Y=X(N+n)
As noted above k=2 is the Calkin-Wilf tree. See
L<Math::PlanePath::RationalsTree/OEIS> for "CW" related sequences.
=head1 SEE ALSO
L<Math::PlanePath>,
L<Math::PlanePath::RationalsTree>,
L<Math::PlanePath::PythagoreanTree>
=head1 HOME PAGE
L<http://user42.tuxfamily.org/math-planepath/index.html>
( run in 0.729 second using v1.01-cache-2.11-cpan-df04353d9ac )