1Math::PlanePath::RationUaslesrTrCeoen(t3r)ibuted Perl DoMcautmhe:n:tPaltainoenPath::RationalsTree(3)
2
6 Math::PlanePath::RationalsTree -- rationals by tree
7
9 use Math::PlanePath::RationalsTree;
10 my $path = Math::PlanePath::RationalsTree->new (tree_type => 'SB');
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This path enumerates reduced rational fractions X/Y > 0, ie. X and Y
15 having no common factor.
16 The rationals are traversed by rows of a binary tree which represents a
18 coprime pair X,Y by steps of a subtraction-only greatest common divisor
19 algorithm which proves them coprime. Or equivalently by bit runs with
20 lengths which are the quotients in the division-based Euclidean GCD
21 algorithm and which are also the terms in the continued fraction
22 representation of X/Y.
23 The SB, CW, AYT, HCS, Bird and Drib trees all have the same set of X/Y
25 rationals in a row, but in a different order due to different encodings
26 of the N value. See the author's mathematical write-up for a proof
27 that these are the only trees with a fixed set of matrices.
28 <http://user42.tuxfamily.org/rationals/index.html>
30 The bit runs mean that N values are quite large for relatively modest
32 sized rationals. For example in the SB tree 167/3 is
33 N=288230376151711741, a 58-bit number. The tendency is for the tree to
34 make excursions out to large rationals while only slowly filling in
35 small ones. The worst is the integer X/1 for which N has X many bits,
36 and similarly 1/Y is Y bits.
37 See examples/rationals-tree.pl for a printout of all the trees.
39 Stern-Brocot Tree
41 The default "tree_type=>"SB"" is the tree of Moritz Stern and Achille
42 Brocot.
43 depth N
45 ----- -------
46 0 1 1/1
47 ------ ------
48 1 2 to 3 1/2 2/1
49 / \ / \
50 2 4 to 7 1/3 2/3 3/2 3/1
51 | | | | | | | |
52 3 8 to 15 1/4 2/5 3/5 3/4 4/3 5/3 5/2 4/1
53 Within a row the fractions increase in value. Each row of the tree is
55 a repeat of the previous row as first X/(X+Y) and then (X+Y)/Y. For
56 example
57 depth=1 1/2, 2/1
59 depth=2 1/3, 2/3 X/(X+Y) of previous row
61 3/2, 3/1 (X+Y)/Y of previous row
62 Plotting the N values by X,Y is as follows. The unused X,Y positions
64 are where X and Y have a common factor. For example X=6,Y=2 has common
65 factor 2 so is never reached.
66 tree_type => "SB"
68 10 | 512 35 44 767
70 9 | 256 33 39 40 46 383 768
71 8 | 128 18 21 191 384
72 7 | 64 17 19 20 22 95 192 49 51
73 6 | 32 47 96
74 5 | 16 9 10 23 48 25 26 55
75 4 | 8 11 24 27 56
76 3 | 4 5 12 13 28 29 60
77 2 | 2 6 14 30 62
78 1 | 1 3 7 15 31 63 127 255 511 1023
79 Y=0 |
80 ----------------------------------------------------
81 X=0 1 2 3 4 5 6 7 8 9 10
82 The X=1 vertical is the fractions 1/Y which is at the left of each tree
84 row, at N value
85 Nstart = 2^depth
87 The Y=1 horizontal is the X/1 integers at the end each row which is
89 Nend = 2^(depth+1)-1
91 Numbering nodes of the tree by rows starting from 1 means N without the
93 high 1 bit is the offset into the row. For example binary N="1011" is
94 "011"=3 into the row. Those bits after the high 1 are also the
95 directions to follow down the tree to a node, with 0=left and 1=right.
96 So N="1011" binary goes from the root 0=left then twice 1=right to
97 reach X/Y=3/4 at N=11 decimal.
98 Stern-Brocot Mediant
100 Writing the parents between the children as an "in-order" tree
101 traversal to a given depth has all values in increasing order (the same
102 as each row individually is in increasing order).
103 1/1
105 1/2 | 2/1
106 1/3 | 2/3 | 3/2 | 3/1
107 | | | | | | |
108 1/3 1/2 2/3 1/1 3/2 2/1 3/1
110 ^
111 |
112 next level (1+3)/(1+2) = 4/3 mediant
113 New values at the next level of this flattening are a "mediant"
115 (x1+x2)/(y1+y2) formed from the left and right parent. So the next
116 level 4/3 shown is left parent 1/1 and right parent 3/2 giving mediant
117 (1+3)/(1+2)=4/3. At the left end a preceding 0/1 is imagined. At the
118 right end a following 1/0 is imagined, so as to have 1/(depth+1) and
119 (depth+1)/1 at the ends for a total 2^depth many new values.
120 The turn sequence left or right along the row depth >= 2 is by a
122 repeating LRRL pattern, except the first and last are always R. (See
123 the author's mathematical write-up for details.)
124 RRRL,LRRL,LRRL,LRRL,LRRL,LRRL,LRRL,LRRR # row N=32 to N=63
126 Calkin-Wilf Tree
128 "tree_type=>"CW"" selects the tree of Calkin and Wilf,
129 Neil Calkin and Herbert Wilf, "Recounting the Rationals", American
131 Mathematical Monthly, volume 107, number 4, April 2000, pages
132 360-363.
133 <http://www.math.upenn.edu/~wilf/reprints.html>,
135 <http://www.math.upenn.edu/~wilf/website/recounting.pdf>,
136 <http://www.jstor.org/stable/2589182>
137 As noted above, the values within each row are the same as the Stern-
139 Brocot, but in a different order.
140 N=1 1/1
142 ------ ------
143 N=2 to N=3 1/2 2/1
144 / \ / \
145 N=4 to N=7 1/3 3/2 2/3 3/1
146 | | | | | | | |
147 N=8 to N=15 1/4 4/3 3/5 5/2 2/5 5/3 3/4 4/1
148 Going by rows the denominator of one value becomes the numerator of the
150 next. So at 4/3 the denominator 3 becomes the numerator of 3/5 to the
151 right. These values are Stern's diatomic sequence.
152 Each row is symmetric in reciprocals, ie. reading from right to left is
154 the reciprocals of reading left to right. The numerators read left to
155 right are the denominators read right to left.
156 A node descends as
158 X/Y
160 / \
161 X/(X+Y) (X+Y)/Y
162 Taking these formulas in reverse up the tree shows how it relates to a
164 subtraction-only greatest common divisor. At a given node the smaller
165 of P or Q is subtracted from the bigger,
166 P/(Q-P) (P-Q)/P
168 / or \
169 P/Q P/Q
170 Plotting the N values by X,Y is as follows. The X=1 vertical and Y=1
172 horizontal are the same as the SB above, but the values in between are
173 re-ordered.
174 tree_type => "CW"
176 10 | 512 56 38 1022
178 9 | 256 48 60 34 46 510 513
179 8 | 128 20 26 254 257
180 7 | 64 24 28 18 22 126 129 49 57
181 6 | 32 62 65
182 5 | 16 12 10 30 33 25 21 61
183 4 | 8 14 17 29 35
184 3 | 4 6 9 13 19 27 39
185 2 | 2 5 11 23 47
186 1 | 1 3 7 15 31 63 127 255 511 1023
187 Y=0 |
188 -------------------------------------------------------------
189 X=0 1 2 3 4 5 6 7 8 9 10
190 At each node the left leg is X/(X+Y) < 1 and the right leg is
192 (X+Y)/Y > 1, which means N is even above the X=Y diagonal and odd
193 below. In general each right leg increments the integer part of the
194 fraction,
195 X/Y right leg each time
197 (X+Y)/Y = 1 + X/Y
198 (X+2Y)/Y = 2 + X/Y
199 (X+3Y)/Y = 3 + X/Y
200 etc
201 This means the integer part is the trailing 1-bits of N,
203 floor(X/Y) = count trailing 1-bits of N
205 eg. 7/2 is at N=23 binary "10111"
206 which has 3 trailing 1-bits for floor(7/2)=3
207 N values for the SB and CW trees are converted by reversing bits except
209 the highest. So at a given X,Y position
210 SB N = 1abcde SB <-> CW by reversing bits
212 CW N = 1edcba except the high 1-bit
213 For example at X=3,Y=4 the SB tree has N=11 = "1011" binary and the CW
215 has N=14 binary "1110", a reversal of the bits below the high 1.
216 N to X/Y in the CW tree can be calculated keeping track of just an X,Y
218 pair and descending to X/(X+Y) or (X+Y)/Y using the bits of N from high
219 to low. The relationship between the SB and CW N's means the same can
220 be used to calculate the SB tree by taking the bits of N from low to
221 high instead.
222 See also Math::PlanePath::ChanTree for a generalization of CW to
224 ternary or higher trees, ie. descending to 3 or more children at each
225 node.
226 Yu-Ting and Andreev Tree
228 "tree_type=>"AYT"" selects the tree described independently by Yu-Ting
229 and Andreev.
230 Shen Yu-Ting, "A Natural Enumeration of Non-Negative Rational
232 Numbers -- An Informal Discussion", American Mathematical Monthly,
233 87, 1980, pages 25-29. <http://www.jstor.org/stable/2320374>
234 D. N. Andreev, "On a Wonderful Numbering of Positive Rational
236 Numbers", Matematicheskoe Prosveshchenie, Series 3, volume 1, 1997,
237 pages 126-134 <http://mi.mathnet.ru/mp12>
238 Their constructions are a one-to-one mapping between integer N and
240 rational X/Y as a way of enumerating the rationals. This is not
241 designed to be a tree as such, but the result is the same 2^level rows
242 as the above trees. The X/Y values within each row are the same, but
243 in a different order.
244 N=1 1/1
246 ------ ------
247 N=2 to N=3 2/1 1/2
248 / \ / \
249 N=4 to N=7 3/1 1/3 3/2 2/3
250 | | | | | | | |
251 N=8 to N=15 4/1 1/4 4/3 3/4 5/2 2/5 5/3 3/5
252 Each fraction descends as follows. The left is an increment and the
254 right is reciprocal of the increment.
255 X/Y
257 / \
258 X/Y + 1 1/(X/Y + 1)
259 which means
261 X/Y
263 / \
264 (X+Y)/Y Y/(X+Y)
265 The left leg (X+Y)/Y is the same the CW has on its right leg. But
267 Y/(X+Y) is not the same as the CW (the other there being X/(X+Y)).
268 The left leg increments the integer part, so the integer part is given
270 by (in a fashion similar to CW 1-bits above)
271 floor(X/Y) = count trailing 0-bits of N
273 plus one extra if N=2^k
274 N=2^k is one extra because its trailing 0-bits started from N=1 where
276 floor(1/1)=1 whereas any other odd N starts from some floor(X/Y)=0.
277 The Y/(X+Y) right leg forms the Fibonacci numbers F(k)/F(k+1) at the
279 end of each row, ie. at Nend=2^(level+1)-1. And as noted by Andreev,
280 successive right leg fractions N=4k+1 and N=4k+3 add up to 1,
281 X/Y at N=4k+1 + X/Y at N=4k+3 = 1
283 Eg. 2/5 at N=13 and 3/5 at N=15 add up to 1
284 Plotting the N values by X,Y gives
286 tree_type => "AYT"
288 10 | 513 41 43 515
290 9 | 257 49 37 39 51 259 514
291 8 | 129 29 31 131 258
292 7 | 65 25 21 23 27 67 130 50 42
293 6 | 33 35 66
294 5 | 17 13 15 19 34 26 30 38
295 4 | 9 11 18 22 36
296 3 | 5 7 10 14 20 28 40
297 2 | 3 6 12 24 48
298 1 | 1 2 4 8 16 32 64 128 256 512
299 Y=0 |
300 ----------------------------------------------------
301 X=0 1 2 3 4 5 6 7 8 9 10
302 N=1,2,4,8,etc on the Y=1 horizontal is the X/1 integers at
304 Nstart=2^level=2^X. N=1,3,5,9,etc in the X=1 vertical is the 1/Y
305 fractions. Those fractions always immediately follow the corresponding
306 integer, so N=Nstart+1=2^(Y-1)+1 in that column.
307 In each node the left leg (X+Y)/Y > 1 and the right leg Y/(X+Y) < 1,
309 which means odd N is above the X=Y diagonal and even N is below.
310 The tree structure corresponds to Johannes Kepler's tree of fractions
312 (see Math::PlanePath::FractionsTree). That tree starts from 1/2 and
313 makes fractions A/B with A<B by descending to A/(A+B) and B/(A+B).
314 Those descents are the same as the AYT tree and the two are related
315 simply by
316 A = Y AYT denominator is Kepler numerator
318 B = X+Y AYT sum num+den is the Kepler denominator
319 X = B-A inverse
321 Y = A
322 HCS Continued Fraction
324 "tree_type=>"HCS"" selects continued fraction terms coded as bit runs
325 1000...00 from high to low, as per Paul D. Hanna and independently Czyz
326 and Self.
327 <http://oeis.org/A071766>
329 Jerzy Czyz and William Self, "The Rationals Are Countable: Euclid's
331 Proof", The College Mathematics Journal, volume 34, number 5,
332 November 2003, page 367. <http://www.jstor.org/stable/3595818>
333 <http://www.cut-the-knot.org/do_you_know/countRatsCF.shtml>,
335 <http://www.dm.unito.it/~cerruti/doc-html/tremattine/tre_mattine.pdf>
336 This arises also in a radix=1 variation of Jeffrey Shallit's digit-
338 based continued fraction encoding. See "Radix 1" in
339 Math::PlanePath::CfracDigits.
340 If the continued fraction of X/Y is
342 1
344 X/Y = a + ------------ a >= 0
345 1
346 b + ----------- b,c,etc >= 1
347 1
348 c + -------
349 ... + 1
350 --- z >= 2
351 z
352 then the N value is bit runs of lengths a,b,c etc.
354 N = 1000 1000 1000 ... 1000
356 \--/ \--/ \--/ \--/
357 a+1 b c z-1
358 Each group is 1 or more bits. The +1 in "a+1" makes the first group 1
360 or more bits, since a=0 occurs for any X/Y<=1. The -1 in "z-1" makes
361 the last group 1 or more since z>=2.
362 N=1 1/1
364 ------ ------
365 N=2 to N=3 2/1 1/2
366 / \ / \
367 N=4 to N=7 3/1 3/2 1/3 2/3
368 | | | | | | | |
369 N=8 to N=15 4/1 5/2 4/3 5/3 1/4 2/5 3/4 3/5
370 The result is a bit reversal of the N values in the AYT tree.
372 AYT N = binary "1abcde" AYT <-> HCS bit reversal
374 HCS N = binary "1edcba"
375 For example at X=4,Y=7 the AYT tree is N=11 binary "10111" whereas HCS
377 there has N=30 binary "11110", a reversal of the bits below the high 1.
378 Plotting by X,Y gives
380 tree_type => "HCS"
382 10 | 768 50 58 896
384 9 | 384 49 52 60 57 448 640
385 8 | 192 27 31 224 320
386 7 | 96 25 26 30 29 112 160 41 42
387 6 | 48 56 80
388 5 | 24 13 15 28 40 21 23 44
389 4 | 12 14 20 22 36
390 3 | 6 7 10 11 18 19 34
391 2 | 3 5 9 17 33
392 1 | 1 2 4 8 16 32 64 128 256 512
393 Y=0 |
394 +-----------------------------------------------------
395 X=0 1 2 3 4 5 6 7 8 9 10
396 N=1,2,4,etc in the row Y=1 are powers-of-2, being integers X/1 having
398 just a single group of bits N=1000..000.
399 N=1,3,6,12,etc in the column X=1 are 3*2^(Y-1) corresponding to
401 continued fraction 0 + 1/Y so terms 0,Y making runs 1,Y-1 and so bits
402 N=11000...00.
403 The turn sequence left or right following successive X,Y points is the
405 Thue-Morse sequence. A proof of this can be found in the author's
406 mathematical write-up (above).
407 count 1-bits in N+1 turn at N
409 ------------------- ---------
410 odd right
411 even left
412 Bird Tree
414 "tree_type=>"Bird"" selects the Bird tree,
415 Ralf Hinze, "Functional Pearls: The Bird tree", Journal of
417 Functional Programming, volume 19, issue 5, September 2009, pages
418 491-508. DOI 10.1017/S0956796809990116
419 <http://www.cs.ox.ac.uk/ralf.hinze/publications/Bird.pdf>
420 It's expressed recursively, illustrating Haskell programming features.
422 The left subtree is the tree plus one and take the reciprocal. The
423 right subtree is conversely the reciprocal first then add one,
424 1 1
426 -------- and ---- + 1
427 tree + 1 tree
428 which means Y/(X+Y) and (X+Y)/X taking N bits low to high.
430 N=1 1/1
432 ------ ------
433 N=2 to N=3 1/2 2/1
434 / \ / \
435 N=4 to N=7 2/3 1/3 3/1 3/2
436 | | | | | | | |
437 N=8 to N=15 3/5 3/4 1/4 2/5 5/2 4/1 4/3 5/3
438 Plotting by X,Y gives
440 tree_type => "Bird"
442 10 | 682 41 38 597
444 9 | 341 43 45 34 36 298 938
445 8 | 170 23 16 149 469
446 7 | 85 20 22 17 19 74 234 59 57
447 6 | 42 37 117
448 5 | 21 11 8 18 58 28 31 61
449 4 | 10 9 29 30 50
450 3 | 5 4 14 15 25 24 54
451 2 | 2 7 12 27 52
452 1 | 1 3 6 13 26 53 106 213 426 853
453 Y=0 |
454 ----------------------------------------------------
455 X=0 1 2 3 4 5 6 7 8 9 10
456 Notice that unlike the other trees N=1,2,5,10,etc in the X=1 vertical
458 for fractions 1/Y is not the row start or end, but instead are on a
459 zigzag through the middle of the tree binary N=1010...etc alternate 1
460 and 0 bits. The integers X/1 in the Y=1 vertical are similar, but
461 N=11010...etc starting the alternation from a 1 in the second highest
462 bit, since those integers are in the right hand half of the tree.
463 The Bird tree N values are related to the SB tree by inverting every
465 second bit starting from the second after the high 1-bit,
466 Bird N=1abcdefg.. binary
468 101010.. xor, so b,d,f etc flip 0<->1
469 SB N=1aBcDeFg.. to make B,D,F
470 For example 3/4 in the SB tree is at N=11 = binary 1011. Xor with 0010
472 for binary 1001 N=9 which is 3/4 in the Bird tree. The same xor goes
473 back the other way Bird tree to SB tree.
474 This xoring is a mirroring in the tree, swapping left and right at each
476 level. Only every second bit is inverted because mirroring twice puts
477 it back to the ordinary way on even rows.
478 Drib Tree
480 "tree_type=>"Drib"" selects the Drib tree by Ralf Hinze.
481 <http://oeis.org/A162911>
483 It reverses the bits of N in the Bird tree (in a similar way that the
485 SB and CW are bit reversals of each other).
486 N=1 1/1
488 ------ ------
489 N=2 to N=3 1/2 2/1
490 / \ / \
491 N=4 to N=7 2/3 3/1 1/3 3/2
492 | | | | | | | |
493 N=8 to N=15 3/5 5/2 1/4 4/3 3/4 4/1 2/5 5/3
494 The descendants of each node are
496 X/Y
498 / \
499 Y/(X+Y) (X+Y)/X
500 The endmost fractions of each row are Fibonacci numbers, F(k)/F(k+1) on
502 the left and F(k+1)/F(k) on the right.
503 tree_type => "Drib"
505 10 | 682 50 44 852
507 9 | 426 58 54 40 36 340 683
508 8 | 170 30 16 212 427
509 7 | 106 18 22 24 28 84 171 59 51
510 6 | 42 52 107
511 5 | 26 14 8 20 43 19 31 55
512 4 | 10 12 27 23 41
513 3 | 6 4 11 15 25 17 45
514 2 | 2 7 9 29 37
515 1 | 1 3 5 13 21 53 85 213 341 853
516 Y=0 |
517 -------------------------------------------------------
518 X=0 1 2 3 4 5 6 7 8 9 10
519 In each node descent the left Y/(X+Y) < 1 and the right (X+Y)/X > 1,
521 which means even N is above the X=Y diagonal and odd N is below.
522 Because Drib/Bird are bit reversals like CW/SB are bit reversals, the
524 xor procedure described above which relates Bird<->SB applies to
525 Drib<->CW, but working from the second lowest bit upwards, ie. xor
526 binary "0..01010". For example 4/1 is at N=15 binary 1111 in the CW
527 tree. Xor with 0010 for 1101 N=13 which is 4/1 in the Drib tree.
528 L Tree
530 "tree_type=>"L"" selects the L-tree by Peter Luschny.
531 <http://www.oeis.org/wiki/User:Peter_Luschny/SternsDiatomic>
533 It's a row-reversal of the CW tree with a shift to include zero as 0/1.
535 N=0 0/1
537 ------ ------
538 N=1 to N=2 1/2 1/1
539 / \ / \
540 N=3 to N=8 2/3 3/2 1/3 2/1
541 | | | | | | | |
542 N=9 to N=16 3/4 5/3 2/5 5/2 3/5 4/3 1/4 3/1
543 Notice in the N=9 to N=16 row rationals 3/4 to 1/4 are the same as in
545 the CW tree but read right-to-left.
546 tree_type => "L"
548 10 | 1021 37 55 511
550 9 | 509 45 33 59 47 255 1020
551 8 | 253 25 19 127 508
552 7 | 125 21 17 27 23 63 252 44 36
553 6 | 61 31 124
554 5 | 29 9 11 15 60 20 24 32
555 4 | 13 7 28 16 58
556 3 | 5 3 12 8 26 18 54
557 2 | 1 4 10 22 46
558 1 | 0 2 6 14 30 62 126 254 510 1022 2046
559 Y=0 |
560 -------------------------------------------------------
561 X=0 1 2 3 4 5 6 7 8 9 10
562 N=0,2,6,14,30,etc along the row at Y=1 are powers 2^(X+1)-2.
564 N=1,5,13,29,etc in the column at X=1 are similar powers 2^Y-3.
565 Common Characteristics
567 The SB, CW, Bird, Drib, AYT and HCS trees have the same set of
568 rationals in each row, just in different orders. The properties of
569 Stern's diatomic sequence mean that within a row the totals are
570 row N=2^depth to N=2^(depth+1)-1 inclusive
572 sum X/Y = (3 * 2^depth - 1) / 2
574 sum X = 3^depth
575 sum 1/(X*Y) = 1
576 For example the SB tree depth=2, N=4 to N=7,
578 sum X/Y = 1/3 + 2/3 + 3/2 + 3/1 = 11/2 = (3*2^2-1)/2
580 sum X = 1+2+3+3 = 9 = 3^2
581 sum 1/(X*Y) = 1/(1*3) + 1/(2*3) + 1/(3*2) + 1/(3*1) = 1
582 Many permutations are conceivable within a row, but the ones here have
584 some relationship to X/Y descendants, tree sub-forms or continued
585 fractions. As an encoding of continued fraction terms by bit runs the
586 combinations are
587 bit encoding high to low low to high
589 ---------------- ----------- -----------
590 0000 1111 runs SB CW
591 0101 1010 alternating Bird Drib
592 1000 1000 runs HCS AYT
593 A run of alternating 101010 ends where the next bit is the oppose of
595 the expected alternating 0,1. This is a doubled bit 00 or 11. An
596 electrical engineer would think of it as a phase shift.
597 Minkowski Question Mark
599 The Minkowski question mark function is a sum of the terms in the
600 continued fraction representation of a real number. If q0,q1,q2,etc
601 are those terms then the question mark function "?(r)" is
602 1 1 1
604 ?(r) = 2 * (1 - ---- * (1 - ---- * (1 - ---- * (1 - ...
605 2^q0 2^q1 2^q2
606 1 1 1
608 = 2 * (1 - ---- + --------- - ------------ + ... )
609 2^q0 2^(q0+q1) 2^(q0+q1+q2)
610 For rational r the continued fraction q0,q1,q2,etc is finite and so the
612 ?(r) sum is finite and rational. The pattern of + and - in the terms
613 gives runs of bits the same as the N values in the Stern-Brocot tree.
614 The RationalsTree code can calculate the ?(r) function by
615 rational r=X/Y
617 N = xy_to_n(X,Y) tree_type=>"SB"
618 depth = floor(log2(N)) # row containing N (depth=0 at top)
619 Ndepth = 2^depth # start of row containing N
620 2*(N-Ndepth) + 1
622 ?(r) = ----------------
623 Ndepth
624 The effect of N-Ndepth is to remove the high 1-bit, leaving an offset
626 into the row. 2*(..)+1 appends an extra 1-bit at the end. The
627 division by Ndepth scales down from integer N to a fraction.
628 N = 1abcdef integer, in binary
630 ?(r) = a.bcdef1 binary fraction
631 For example ?(2/3) is X=2,Y=3 which is N=5 in the SB tree. It is at
633 depth=2, Ndepth=2^2=4, and so ?(2/3)=(2*(5-4)+1)/4=3/4. Or written in
634 binary N=101 gives Ndepth=100 and N-Ndepth=01 so 2*(N-Ndepth)+1=011 and
635 divide by Ndepth=100 for ?=0.11.
636 In practice this is not a very efficient way to handle the question
638 function, since the bit runs in the N values may become quite large for
639 relatively modest fractions. (Math::ContinuedFraction may be better,
640 and also allows repeating terms from quadratic irrationals to be
641 represented exactly.)
642 Pythagorean Triples
644 Pythagorean triples A^2+B^2=C^2 can be generated by A=P^2-Q^2, B=2*P*Q.
645 If P>Q>1 with P,Q no common factor and one odd the other even then this
646 gives all primitive triples, being primitive in the sense of A,B,C no
647 common factor ("PQ Coordinates" in Math::PlanePath::PythagoreanTree).
648 In the Calkin-Wilf tree the parity of X,Y pairs are as follows. Pairs
650 X,Y with one odd the other even are N=0 or 2 mod 3.
651 CW tree X/Y
653 --------
654 N=0 mod 3 even/odd
655 N=1 mod 3 odd/odd
656 N=2 mod 3 odd/even
657 This occurs because the numerators are the Stern diatomic sequence and
659 the denominators likewise but offset by 1. The Stern diatomic sequence
660 is a repeating pattern even,odd,odd (eg. per "Odd and Even" in
661 Math::NumSeq::SternDiatomic).
662 The X>Y pairs in the CW tree are the right leg of each node, which is N
664 odd. so
665 CW tree N=3 or 5 mod 6 gives X>Y one odd the other even
667 index t=1,2,3,etc to enumerate such pairs
669 N = 3*t if t odd
670 3*t-1 if t even
671 2 of each 6 points are used. In a given row it's width/3 but rounded
673 up or down according to where the 3,5mod6 falls on the N=2^depth start,
674 which is either floor or ceil according to depth odd or even,
675 NumPQ(depth) = floor(2^depth / 3) for depth=even
677 ceil (2^depth / 3) for depth=odd
678 = 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, ...
679 These are the Jacobsthal numbers, which in binary are 101010...101 and
681 1010...1011.
682 For the other tree types the various bit transformations which map N
684 positions between the trees can be applied to the above N=3or5 mod 6.
685 The simplest is the L tree where the N offset and row reversal gives
686 N=0or4 mod 6.
687 The SB tree is a bit reversal of the CW, as described above, and for
689 the Pythagorean N this gives
690 SB tree N=0 or 2 mod 2 and N="11...." in binary
692 gives X>Y one odd the other even
693 N="11..." binary is the bit reversal of the CW N=odd "1...1" condition.
695 This bit pattern is those N in the second half of each row, which is
696 where the X/Y > 1 rationals occur. The N=0or2 mod 3 condition is
697 unchanged by the bit reversal. N=0or2 mod 3 precisely when
698 bitreverse(N)=0or2 mod 3.
699 For SB whether it's odd/even or even/odd at N=0or2 mod 3 alternates
701 between rows. The two are both wanted, they just happen to switch in
702 each row.
703 SB tree X/Y depth=even depth=odd
705 ---------- ---------
706 N=0 mod 3 odd/even even/odd
707 N=1 mod 3 odd/odd odd/odd <- exclude for Pythagorean
708 N=2 mod 3 even/odd odd/even
709
711 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
712 classes.
713 "$path = Math::PlanePath::RationalsTree->new ()"
715 "$path = Math::PlanePath::RationalsTree->new (tree_type => $str)"
716 Create and return a new path object. "tree_type" (a string) can be
717 "SB" Stern-Brocot
719 "CW" Calkin-Wilf
720 "AYT" Yu-Ting, Andreev
721 "HCS"
722 "Bird"
723 "Drib"
724 "L"
725 "$n = $path->n_start()"
727 Return the first N in the path. This is 1 for SB, CW, AYT, HCS,
728 Bird and Drib, but 0 for L.
729 "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
731 Return a range of N values which occur in a rectangle with corners
732 at $x1,$y1 and $x2,$y2. The range is inclusive.
733 For reference, $n_hi can be quite large because within each row
735 there's only one new X/1 integer and 1/Y fraction. So if X=1 or
736 Y=1 is included then roughly "$n_hi = 2**max(x,y)". If min(x,y) is
737 bigger than 1 then it reduces a little to roughly 2**(max/min +
738 min).
739 Tree Methods
741 Each point has 2 children, so the path is a complete binary tree.
742 "@n_children = $path->tree_n_children($n)"
744 Return the two children of $n, or an empty list if "$n < 1" (ie.
745 before the start of the path).
746 This is simply "2*$n, 2*$n+1". Written in binary the children are
748 $n with an extra bit appended, a 0-bit or a 1-bit.
749 "$num = $path->tree_n_num_children($n)"
751 Return 2, since every node has two children. If "$n<1", ie. before
752 the start of the path, then return "undef".
753 "$n_parent = $path->tree_n_parent($n)"
755 Return the parent node of $n. Or return "undef" if "$n <= 1" (the
756 top of the tree).
757 This is simply Nparent = floor(N/2), ie. strip the least
759 significant bit from $n. (Undo what "tree_n_children()" appends.)
760 "$depth = $path->tree_n_to_depth($n)"
762 Return the depth of node $n, or "undef" if there's no point $n.
763 The top of the tree at N=1 is depth=0, then its children depth=1,
764 etc.
765 This is simply floor(log2(N)) since the tree has 2 nodes per point.
767 For example N=4 through N=7 are all depth=2.
768 The L tree starts at N=0 and the calculation becomes
770 floor(log2(N+1)) there.
771 "$n = $path->tree_depth_to_n($depth)"
773 "$n = $path->tree_depth_to_n_end($depth)"
774 Return the first or last N at tree level $depth in the path, or
775 "undef" if nothing at that depth or not a tree. The top of the
776 tree is depth=0.
777 The structure of the tree means the first N is at "2**$depth", or
779 for the L tree "2**$depth - 1". The last N is "2**($depth+1)-1",
780 or for the L tree "2**($depth+1)".
781 Tree Descriptive Methods
783 "$num = $path->tree_num_children_minimum()"
784 "$num = $path->tree_num_children_maximum()"
785 Return 2 since every node has 2 children so that's both the minimum
786 and maximum.
787 "$bool = $path->tree_any_leaf()"
789 Return false, since there are no leaf nodes in the tree.
790
792 The trees are in Sloane's Online Encyclopedia of Integer Sequences in
793 various forms,
794 <http://oeis.org/A007305> (etc)
796 tree_type=SB
798 A007305 X, extra initial 0,1
799 A047679 Y
800 A057431 X,Y pairs (initial extra 0/1,1/0)
801 A007306 X+Y sum, Farey 0 to 1 part (extra 1,1)
802 A153036 int(X/Y), integer part
803 A088696 length of continued fraction SB left half (X/Y<1)
804 A153778 X mod 2
805 A004755 N of frac+1, so X+Y,Y
806 tree_type=CW
808 A002487 X and Y, Stern diatomic sequence (extra 0)
809 A070990 Y-X diff, Stern diatomic first diffs (less 0)
810 A070871 X*Y product
811 A007814 int(X/Y), integer part, count trailing 1-bits
812 which is count trailing 0-bits of N+1
813 A086893 N position of Fibonacci F[n+1]/F[n], N = binary 1010..101
814 A061547 N position of Fibonacci F[n]/F[n+1], N = binary 11010..10
815 A047270 3or5 mod 6, being N positions of X>Y not both odd
816 which can generate primitive Pythagorean triples
817 tree_type=AYT
819 A020650 X
820 A020651 Y (Kepler numerator)
821 A086592 X+Y sum (Kepler denominator)
822 A135523 int(X/Y), integer part,
823 count trailing 0-bits plus 1 extra if N=2^k
824 tree_type=HCS
826 A229742 X, extra initial 0/1
827 A071766 Y
828 A071585 X+Y sum
829 tree_type=Bird
831 A162909 X
832 A162910 Y
833 A081254 N of row Y=1, N = binary 1101010...10
834 A000975 N of column X=1, N = binary 101010...10
835 tree_type=Drib
837 A162911 X
838 A162912 Y
839 A086893 N of row Y=1, N = binary 110101..0101 (ending 1)
840 A061547 N of column X=1, N = binary 110101..010 (ending 0)
841 tree_type=L
843 A174981 X
844 A002487 Y, same as CW X,Y, Stern diatomic
845 A047233 0or4 mod 6, being N positions of X>Y not both odd
846 which can generate primitive Pythagorean triples
847 tree_type=SB,CW,AYT,HCS,Bird,Drib,L
849 A008776 total X+Y in row, being 2*3^depth
850 A000523 tree_n_to_depth(), being floor(log2(N))
852 A059893 permutation SB<->CW, AYT<->HCS, Bird<->Drib
854 reverse bits below highest
855 A258746 permutation SB<->Bird,
856 flip every second bit, from 3rd highest downward
857 A003188 permutation SB->HCS, Gray code shift+xor
858 A006068 permutation HCS->SB, Gray code inverse
859 A154435 permutation HCS->Bird, Lamplighter bit flips
860 A154436 permutation Bird->HCS, Lamplighter variant
861 A258996 permutation CW<->Drib, phase shift code high to low
863 A153153 permutation CW->AYT, reverse and un-Gray
864 A153154 permutation AYT->CW, reverse and Gray code
865 A154437 permutation AYT->Drib, Lamplighter low to high
866 A154438 permutation Drib->AYT, un-Lamplighter low to high
867 A054429 permutation SB,CW,Bird,Drib N at transpose Y/X,
869 (mirror binary tree, runs 0b11..11 down to 0b10..00)
870 A004442 permutation AYT N at transpose Y/X, from N=2 onwards
871 (xor 1, ie. flip least significant bit)
872 A063946 permutation HCS N at transpose Y/X, extra initial 0
873 (xor 2, ie. flip second least significant bit)
874 A054424 permutation DiagonalRationals -> SB
876 A054426 permutation SB -> DiagonalRationals
877 A054425 DiagonalRationals -> SB with 0s at non-coprimes
878 A054427 permutation coprimes -> SB right hand X/Y>1
879 A044051 N+1 of those N where SB and CW have same X,Y
881 same Bird<->Drib and HCS<->AYT
882 begin N+1 of N binary palindrome below high 1-bit
883 The sequences marked "extra ..." have one or two extra initial values
885 over what the RationalsTree here gives, but are the same after that.
886 And the Stern first differences "less ..." means it has one less term
887 than what the code here gives.
888
890 Math::PlanePath, Math::PlanePath::FractionsTree,
891 Math::PlanePath::CfracDigits, Math::PlanePath::ChanTree
892 Math::PlanePath::CoprimeColumns, Math::PlanePath::DiagonalRationals,
894 Math::PlanePath::FactorRationals, Math::PlanePath::GcdRationals,
895 Math::PlanePath::PythagoreanTree
896 Math::NumSeq::SternDiatomic, Math::ContinuedFraction
898
900 <http://user42.tuxfamily.org/math-planepath/index.html>
901
903 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
904 Kevin Ryde
905 This file is part of Math-PlanePath.
907 Math-PlanePath is free software; you can redistribute it and/or modify
909 it under the terms of the GNU General Public License as published by
910 the Free Software Foundation; either version 3, or (at your option) any
911 later version.
912 Math-PlanePath is distributed in the hope that it will be useful, but
914 WITHOUT ANY WARRANTY; without even the implied warranty of
915 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
916 General Public License for more details.
917 You should have received a copy of the GNU General Public License along
919 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
920perl v5.32.1 2021-01-27 Math::PlanePath::RationalsTree(3)