1Math::PlanePath::ChanTrUesee(r3)Contributed Perl DocumenMtaatthi:o:nPlanePath::ChanTree(3)
2
6 Math::PlanePath::ChanTree -- tree of rationals
7
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
14 This path enumerates rationals X/Y in a tree as per
15 Song Heng Chan, "Analogs of the Stern Sequence", Integers 2011,
17 <http://www.integers-ejcnt.org/l26/l26.pdf>
18 The default k=3 visits X,Y with one odd, one even, and perhaps a common
20 factor 3^m.
21 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 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 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 N=26 ...
52 The children of each node are
54 X/Y
56 ------------/ | \-----------
57 | | |
58 X/(2X+Y) (2X+Y)/(X+2Y) (X+2Y)/Y
59 Which as X,Y coordinates means vertical, 45-degree diagonal, and
61 horizontal.
62 X,Y+2X X+(X+Y),Y+(X+Y)
64 | /
65 | /
66 | /
67 | /
68 X,Y------- X+2Y,Y
69 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 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 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 GCD(X,Y) = 3^m
86 m <= count ternary 1-digits of N+1, excluding high digit
87 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 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 For various points the power m is equal to the count of 1-digits.
99 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 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 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 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 k X/Y top nodes
117 --- ---------------------------------
118 k=2 1/1
119 k=3 1/2 2/1
121 k=4 1/2 2/2 2/1
122 k=5 1/2 2/3 3/2 2/1
124 k=6 1/2 2/3 3/3 3/2 2/1
125 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 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 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 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 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 k=5 k=6
159 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 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 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 Chan shows that this combination of top nodes and children visits
178 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 if k even: all rationals X/Y
183 possible GCD(X,Y) a divisor of (k/2)^m
184 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 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 "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 N=1 to 9 1/2 ... ... 2/1
200 N=10 to 99 1/4 4/7 ... ... 7/4 4/1
202 N=100 to 999 1/6 6/11 ... ... 11/6 6/1
204 In general "n_start=>1" makes the tree
206 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 And the high digit of N selects which top-level tree the given N is
214 under, so
215 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 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 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 k=2, Calkin-Wilf tree
237 X/Y
239 / \
240 (1X+0Y)/(1X+1Y) (1X+1Y)/(0X+1Y)
241 = X/(X+Y) = (X+Y)/Y
242
244 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
245 classes.
246 "$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 "$n = $path->n_start()"
253 Return the first N in the path. This is 0 by default, otherwise
254 the "n_start" parameter.
255 "$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 Tree Methods
261 Each point has k children, so the path is a complete k-ary tree.
262 "@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 "$num = $path->tree_n_num_children($n)"
268 Return k, since every node has k children. Or return "undef" if
269 "$n < n_start()", ie. before the start of the path.
270 "$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 "$n_root = $path->tree_n_root ($n)"
276 Return the N which is root node of $n.
277 "$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 "$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 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 "@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 "$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 "$bool = $path->tree_any_leaf()"
304 Return false, since there are no leaf nodes in the tree.
305
307 N Children
308 For the default k=3 the children are
309 3N+2, 3N+3, 3N+4 n_start=0
311 If "n_start=>1" then instead
313 3N, 3N+1, 3N+2 n_start=1
315 For this "n_start=1" the children are found by appending an extra
317 ternary digit, or base-k digit for arbitrary k.
318 k*N, k*N+1, ... , k*N+(k-1) n_start=1
320 In general for k and Nstart the children are
322 kN - (k-1)*(Nstart-1) + 0
324 ...
325 kN - (k-1)*(Nstart-1) + k-1
326 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 parent = floor(N/k) when n_start=1
333 For other "n_start" adjust before and after to an "n_start=1" basis,
335 parent = floor((N-(Nstart-1)) / k) + Nstart-1
337 For example in the default k=0 Nstart=1 the parent of N=3 is
339 floor((3-(1-1))/3)=1.
340 The post-adjustment can be worked into the formula with
342 (k-1)*(Nstart-1) similar to the children above,
343 parent = floor((N + (k-1)*(Nstart-1)) / k)
345 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 N-(Nstart-1) >= k to check N is past top-nodes
350 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 adjust = Nstart-1
357 Nroot(N) = high_base_k_digit(N-adjust) + adjust
358 N to Depth
360 The structure of the tree means
361 depth = floor(logk(N+1)) for n_start=0
363 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 depth = floor(logk(N-(Nstart-1)))
368 "n_start=1" is the simplest case, being the length of N written in
370 base-k digits.
371 depth = floor(logk(N)) for n_start=1
373
375 This tree is in Sloane's Online Encyclopedia of Integer Sequences as
376 <http://oeis.org/A191379> (etc)
378 k=3, n_start=0 (the defaults)
380 A191379 X coordinate, and Y=X(N+n)
381 As noted above k=2 is the Calkin-Wilf tree. See "OEIS" in
383 Math::PlanePath::RationalsTree for "CW" related sequences.
384
386 Math::PlanePath, Math::PlanePath::RationalsTree,
387 Math::PlanePath::PythagoreanTree
388
390 <http://user42.tuxfamily.org/math-planepath/index.html>
391
393 Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019 Kevin Ryde
394 This file is part of Math-PlanePath.
396 Math-PlanePath is free software; you can redistribute it and/or modify
398 it under the terms of the GNU General Public License as published by
399 the Free Software Foundation; either version 3, or (at your option) any
400 later version.
401 Math-PlanePath is distributed in the hope that it will be useful, but
403 WITHOUT ANY WARRANTY; without even the implied warranty of
404 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
405 General Public License for more details.
406 You should have received a copy of the GNU General Public License along
408 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
409perl v5.32.0 2020-07-28 Math::PlanePath::ChanTree(3)