1Math::PlanePath::ChanTrUesee(r3)Contributed Perl DocumenMtaatthi:o:nPlanePath::ChanTree(3)
2
3
4

NAME

6       Math::PlanePath::ChanTree -- tree of rationals
7

SYNOPSIS

9        use Math::PlanePath::ChanTree;
10        my $path = Math::PlanePath::ChanTree->new (k => 3, reduced => 0);
11        my ($x, $y) = $path->n_to_xy (123);
12

DESCRIPTION

14       This path enumerates rationals X/Y in a tree as per
15
16           Song Heng Chan, "Analogs of the Stern Sequence", Integers 2011,
17           <http://www.integers-ejcnt.org/l26/l26.pdf>
18
19       The default k=3 visits X,Y with one odd, one even, and perhaps a common
20       factor 3^m.
21
22            14 |    728              20                              12
23            13 |         53      11      77      27
24            12 |    242              14              18
25            11 |
26            10 |     80
27             9 |         17      23       9                      15
28             8 |     26                                              78
29             7 |
30             6 |      8                              24              28
31             5 |          5       3                              19
32             4 |      2               6              10              22
33             3 |
34             2 |      0               4              16              52
35             1 |          1       7      25      79     241     727
36           Y=0 |
37               +--------------------------------------------------------
38                X=0   1   2   3   4   5   6   7   8   9  10  11  12  13
39
40       There are 2 tree roots (so technically it's a "forest") and each node
41       has 3 children.  The points are numbered by rows starting from N=0.
42       This numbering corresponds to powers in a polynomial product generating
43       function.
44
45           N=0 to 1               1/2                    2/1
46                                /  |  \                /  |  \
47           N=2 to 7          1/4  4/5   5/2         2/5  5/4  4/1
48                            / | \  ...   ...      ...   ...  / | \
49           N=8 to 25     1/6 6/9 9/4  ...            ...  5/9 9/6 6/1
50
51           N=26 ...
52
53       The children of each node are
54
55                           X/Y
56              ------------/ | \-----------
57             |              |             |
58           X/(2X+Y)   (2X+Y)/(X+2Y)   (X+2Y)/Y
59
60       Which as X,Y coordinates means vertical, 45-degree diagonal, and
61       horizontal.
62
63           X,Y+2X      X+(X+Y),Y+(X+Y)
64             |       /
65             |     /
66             |   /
67             | /
68            X,Y------- X+2Y,Y
69
70       The slowest growth is on the far left of the tree 1/2, 1/4, 1/6, 1/8,
71       etc advancing by just 2 at each level.  Similarly on the far right 2/1,
72       4/1, 6/1, etc.  This means that to cover such an X or Y requires a
73       power-of-3, N=3^(max(X,Y)/2).
74
75   GCD
76       Chan shows that these top nodes and children visit all rationals X/Y
77       with X,Y one odd, one even.  But the X,Y are not in least terms, they
78       may have a power-of-3 common factor GCD(X,Y)=3^m for some m.
79
80       The GCD is unchanged in the first and third children.  The middle child
81       GCD might gain an extra factor 3.  This means the power is at most the
82       number of middle legs taken, which is the count of ternary 1-digits of
83       its position across the row.
84
85           GCD(X,Y) = 3^m
86           m <= count ternary 1-digits of N+1, excluding high digit
87
88       As per "N Start" below, N+1 in ternary has high digit 1 or 2 which
89       indicates the tree root.  Ignoring that high digit gives an offset into
90       the row of that tree and the digits are 0,1,2 for left,middle,right.
91
92       For example the first GCD is at N=9 with X=6,Y=9 common factor GCD=3.
93       N+1=10="101" ternary, which without the high digit is "01" which has a
94       single "1" so GCD <= 3^1.  The mirror image of this point is X=9,Y=6 at
95       N=24 and there N+1=24+1=25="221" ternary which without the high digit
96       is "21" with a single 1-digit likewise.
97
98       For various points the power m is equal to the count of 1-digits.
99
100   k Parameter
101       Parameter "k => $integer" controls the number of children and top
102       nodes.  There are k-1 top nodes and each node has k children.  The top
103       nodes are
104
105           k odd, k-1 many tops, with h=ceil(k/2)
106           1/2  2/3  3/4  ... (h-1)/h       h/(h-1) ...  4/3  3/2  2/1
107
108           k even, k-1 many tops, with h=k/2
109           1/2  2/3  3/4  ... (h-1)/h  h/h  h/(h-1) ...  4/3  3/2  2/1
110
111       Notice the list for k odd or k even is the same except that for k even
112       there's an extra middle term h/h.  The first few tops are as follows.
113       The list in each row is spread to show how successive bigger h adds
114       terms in the middle.
115
116            k                 X/Y top nodes
117           ---    ---------------------------------
118           k=2                   1/1
119
120           k=3              1/2       2/1
121           k=4              1/2  2/2  2/1
122
123           k=5         1/2  2/3       3/2  2/1
124           k=6         1/2  2/3  3/3  3/2  2/1
125
126           k=7    1/2  2/3  3/4       4/3  3/2  2/1
127           k=8    1/2  2/3  3/4  4/4  4/3  3/2  2/1
128
129       As X,Y coordinates these tops are a run up along X=Y-1 and back down
130       along X=Y+1, with a middle X=Y point if k even.  For example,
131
132             7 |                         5         k=13 top nodes N=0 to N=11
133             6 |                     4       6        total 12 top nodes
134             5 |                 3       7
135             4 |             2       8
136             3 |         1       9
137             2 |     0      10
138             1 |        11
139           Y=0 |
140               +------------------------------
141               X=0   1   2   3   4   5   6   7
142
143                                                   k=14 top nodes N=0 to N=12
144             7 |                         5   6        total 13 top nodes
145             6 |                     4       7
146             5 |                 3       8         N=6 is the 7/7 middle term
147             4 |             2       9
148             3 |         1      10
149             2 |     0      11
150             1 |        12
151           Y=0 |
152               +------------------------------
153               X=0   1   2   3   4   5   6   7
154
155       Each node has k children.  The formulas for the children can be seen
156       from sample cases k=5 and k=6.  A node X/Y descends to
157
158           k=5                     k=6
159
160           1X+0Y / 2X+1Y           1X+0Y / 2X+1Y
161           2X+1Y / 3X+2Y           2X+1Y / 3X+2Y
162           3X+2Y / 2X+3Y           3X+2Y / 3X+3Y
163           2X+3Y / 1X+2Y           3X+3Y / 2X+3Y
164           1X+2Y / 0X+1Y           2X+3Y / 1X+2Y
165                                   1X+2Y / 0X+1Y
166
167       The coefficients of X and Y run up to h=ceil(k/2) starting from either
168       0, 1 or 2 and ending 2, 1 or 0.  When k is even there's two h coeffs in
169       the middle.  When k is odd there's just one.  The resulting tree for
170       example with k=4 is
171
172           k=4
173                 1/2              2/2               2/1
174              /       \        /        \        /       \
175           1/4 4/6 6/5 5/2  2/6 6/8 8/6 6/2   2/5 5/6 6/4 4/1
176
177       Chan shows that this combination of top nodes and children visits
178
179           if k odd:    rationals X/Y with X,Y one odd, one even
180                         possible GCD(X,Y)=k^m for some integer m
181
182           if k even:   all rationals X/Y
183                         possible GCD(X,Y) a divisor of (k/2)^m
184
185       When k odd, GCD(X,Y) is a power of k, so for example as described above
186       k=3 gives GCD=3^m.  When k even GCD(X,Y) is a divisor of (k/2)^m but
187       not necessarily a full such power.  For example with k=12 the first
188       such non-power GCD is at N=17 where X=16,Y=18 has GCD(16,18)=2 which is
189       only a divisor of k/2=6, not a power of 6.
190
191   N Start
192       The "n_start => $n" option can select a different initial N.  The tree
193       structure is unchanged, just the numbering shifted.  As noted above the
194       default Nstart=0 corresponds to powers in a generating function.
195
196       "n_start=>1" makes the numbering correspond to digits of N written in
197       base-k.  For example k=10 corresponds to N written in decimal,
198
199           N=1 to 9                1/2    ...  ...    2/1
200
201           N=10 to 99          1/4 4/7  ...      ...  7/4 4/1
202
203           N=100 to 999    1/6 6/11   ...          ...   11/6 6/1
204
205       In general "n_start=>1" makes the tree
206
207           N written in base-k digits
208            depth = numdigits(N)-1
209            NdepthStart = k^depth
210                        = 100..000 base-k, high 1 in high digit position of N
211            N-NdepthStart = position across whole row of all top trees
212
213       And the high digit of N selects which top-level tree the given N is
214       under, so
215
216           N written in base-k digits
217            top tree = high digit of N
218                       (1 to k, selecting the k-1 many top nodes)
219            Nrem = digits of N after the highest
220                 = position across row within the high-digit tree
221            depth = numdigits(Nrem)       # top node depth=0
222                  = numdigits(N)-1
223
224   Diatomic Sequence
225       Chan shows that each denominator Y becomes the numerator X in the next
226       point.  The last Y of a row becomes the first X of the next row.  This
227       is a generalization of Stern's diatomic sequence and of the Calkin-Wilf
228       tree of rationals.  (See Math::NumSeq::SternDiatomic and "Calkin-Wilf
229       Tree" in Math::PlanePath::RationalsTree.)
230
231       The case k=2 is precisely the Calkin-Wilf tree.  There's just one top
232       node 1/1, being the even k "middle" form h/h with h=k/2=1 as described
233       above.  Then there's two children of each node (the "middle" pair of
234       the even k case),
235
236           k=2, Calkin-Wilf tree
237
238                            X/Y
239                          /     \
240           (1X+0Y)/(1X+1Y)       (1X+1Y)/(0X+1Y)
241              = X/(X+Y)             = (X+Y)/Y
242

FUNCTIONS

244       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
245       classes.
246
247       "$path = Math::PlanePath::ChanTree->new ()"
248       "$path = Math::PlanePath::ChanTree->new (k => $k, n_start => $n)"
249           Create and return a new path object.  The defaults are k=3 and
250           n_start=0.
251
252       "$n = $path->n_start()"
253           Return the first N in the path.  This is 0 by default, otherwise
254           the "n_start" parameter.
255
256       "$n = $path->xy_to_n ($x,$y)"
257           Return the point number for coordinates "$x,$y".  If there's
258           nothing at "$x,$y" then return "undef".
259
260   Tree Methods
261       Each point has k children, so the path is a complete k-ary tree.
262
263       "@n_children = $path->tree_n_children($n)"
264           Return the children of $n, or an empty list if "$n < n_start()",
265           ie. before the start of the path.
266
267       "$num = $path->tree_n_num_children($n)"
268           Return k, since every node has k children.  Or return "undef" if $n
269           < n_start(), ie. before the start of the path.
270
271       "$n_parent = $path->tree_n_parent($n)"
272           Return the parent node of $n, or "undef" if $n has no parent either
273           because it's a top node or before n_start().
274
275       "$n_root = $path->tree_n_root ($n)"
276           Return the N which is root node of $n.
277
278       "$depth = $path->tree_n_to_depth($n)"
279           Return the depth of node $n, or "undef" if there's no point $n.
280           The tree tops are depth=0, then their children depth=1, etc.
281
282       "$n = $path->tree_depth_to_n($depth)"
283       "$n = $path->tree_depth_to_n_end($depth)"
284           Return the first or last N at tree level $depth in the path.  The
285           top of the tree is depth=0.
286
287   Tree Descriptive Methods
288       "$num = $path->tree_num_roots ()"
289           Return the number of root nodes in $path, which is k-1.  For
290           example the default k=3 return 2 as there are two root nodes.
291
292       "@n_list = $path->tree_root_n_list ()"
293           Return a list of the N values which are the root nodes of $path.
294           This is n_start() through "n_start()+k-2" inclusive, being the
295           first k-1 many points.  For example in the default k=2 and Nstart=0
296           the return is two values "(0,1)".
297
298       "$num = $path->tree_num_children_minimum()"
299       "$num = $path->tree_num_children_maximum()"
300           Return k since every node has k many children, making that both the
301           minimum and maximum.
302
303       "$bool = $path->tree_any_leaf()"
304           Return false, since there are no leaf nodes in the tree.
305

FORMULAS

307   N Children
308       For the default k=3 the children are
309
310           3N+2, 3N+3, 3N+4        n_start=0
311
312       If "n_start=>1" then instead
313
314           3N, 3N+1, 3N+2                  n_start=1
315
316       For this "n_start=1" the children are found by appending an extra
317       ternary digit, or base-k digit for arbitrary k.
318
319           k*N, k*N+1, ... , k*N+(k-1)     n_start=1
320
321       In general for k and Nstart the children are
322
323           kN - (k-1)*(Nstart-1)  + 0
324             ...
325           kN - (k-1)*(Nstart-1)  + k-1
326
327   N Parent
328       The parent node reverses the children calculation above.  The simplest
329       case is "n_start=1" where it's a division to remove the lowest base-k
330       digit
331
332           parent = floor(N/k)       when n_start=1
333
334       For other "n_start" adjust before and after to an "n_start=1" basis,
335
336           parent = floor((N-(Nstart-1)) / k) + Nstart-1
337
338       For example in the default k=0 Nstart=1 the parent of N=3 is
339       floor((3-(1-1))/3)=1.
340
341       The post-adjustment can be worked into the formula with
342       (k-1)*(Nstart-1) similar to the children above,
343
344           parent = floor((N + (k-1)*(Nstart-1)) / k)
345
346       But the first style is more convenient to compare to see that N is past
347       the top nodes and therefore has a parent.
348
349           N-(Nstart-1) >= k      to check N is past top-nodes
350
351   N Root
352       As described under "N Start" above, if Nstart=1 then the tree root is
353       simply the most significant base-k digit of N.  For other Nstart an
354       adjustment is made to N=1 style and back again.
355
356           adjust = Nstart-1
357           Nroot(N) = high_base_k_digit(N-adjust) + adjust
358
359   N to Depth
360       The structure of the tree means
361
362           depth = floor(logk(N+1))    for n_start=0
363
364       For example if k=3 then all of N=8 through N=25 inclusive have
365       depth=floor(log3(N+1))=2.  With an "n_start" it becomes
366
367           depth = floor(logk(N-(Nstart-1)))
368
369       "n_start=1" is the simplest case, being the length of N written in
370       base-k digits.
371
372           depth = floor(logk(N))     for n_start=1
373

OEIS

375       This tree is in Sloane's Online Encyclopedia of Integer Sequences as
376
377           <http://oeis.org/A191379> (etc)
378
379           k=3, n_start=0  (the defaults)
380             A191379   X coordinate, and Y=X(N+n)
381
382       As noted above k=2 is the Calkin-Wilf tree.  See "OEIS" in
383       Math::PlanePath::RationalsTree for "CW" related sequences.
384

SEE ALSO

386       Math::PlanePath, Math::PlanePath::RationalsTree,
387       Math::PlanePath::PythagoreanTree
388

HOME PAGE

390       <http://user42.tuxfamily.org/math-planepath/index.html>
391

LICENSE

393       Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin
394       Ryde
395
396       This file is part of Math-PlanePath.
397
398       Math-PlanePath is free software; you can redistribute it and/or modify
399       it under the terms of the GNU General Public License as published by
400       the Free Software Foundation; either version 3, or (at your option) any
401       later version.
402
403       Math-PlanePath is distributed in the hope that it will be useful, but
404       WITHOUT ANY WARRANTY; without even the implied warranty of
405       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
406       General Public License for more details.
407
408       You should have received a copy of the GNU General Public License along
409       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
410
411
412
413perl v5.38.0                      2023-07-20      Math::PlanePath::ChanTree(3)
Impressum