1Math::PlanePath::RationUaslesrTrCeoen(t3r)ibuted Perl DoMcautmhe:n:tPaltainoenPath::RationalsTree(3)
2
3
4

NAME

6       Math::PlanePath::RationalsTree -- rationals by tree
7

SYNOPSIS

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

DESCRIPTION

14       This path enumerates reduced rational fractions X/Y > 0, ie. X and Y
15       having no common factor.
16
17       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
24       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
29           <http://user42.tuxfamily.org/rationals/index.html>
30
31       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
38       See examples/rationals-tree.pl for a printout of all the trees.
39
40   Stern-Brocot Tree
41       The default "tree_type=>"SB"" is the tree of Moritz Stern and Achille
42       Brocot.
43
44           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
54       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
58           depth=1    1/2, 2/1
59
60           depth=2    1/3, 2/3    X/(X+Y) of previous row
61                      3/2, 3/1    (X+Y)/Y of previous row
62
63       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
67           tree_type => "SB"
68
69           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
83       The X=1 vertical is the fractions 1/Y which is at the left of each tree
84       row, at N value
85
86           Nstart = 2^depth
87
88       The Y=1 horizontal is the X/1 integers at the end each row which is
89
90           Nend = 2^(depth+1)-1
91
92       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
99   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
104                        1/1
105                1/2      |      2/1
106            1/3  |  2/3  |  3/2  |  3/1
107             |   |   |   |   |   |   |
108
109            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
114       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
121       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
125           RRRL,LRRL,LRRL,LRRL,LRRL,LRRL,LRRL,LRRR   # row N=32 to N=63
126
127   Calkin-Wilf Tree
128       "tree_type=>"CW"" selects the tree of Calkin and Wilf,
129
130           Neil Calkin and Herbert Wilf, "Recounting the Rationals", American
131           Mathematical Monthly, volume 107, number 4, April 2000, pages
132           360-363.
133
134           <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
138       As noted above, the values within each row are the same as the Stern-
139       Brocot, but in a different order.
140
141           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
149       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
153       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
157       A node descends as
158
159                 X/Y
160               /     \
161           X/(X+Y)  (X+Y)/Y
162
163       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
167              P/(Q-P)         (P-Q)/P
168             /          or        \
169           P/Q                    P/Q
170
171       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
175           tree_type => "CW"
176
177           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
191       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
196           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
202       This means the integer part is the trailing 1-bits of N,
203
204           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
208       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
211           SB  N = 1abcde         SB <-> CW by reversing bits
212           CW  N = 1edcba         except the high 1-bit
213
214       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
217       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
223       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
227   Yu-Ting and Andreev Tree
228       "tree_type=>"AYT"" selects the tree described independently by Yu-Ting
229       and Andreev.
230
231           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
235           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
239       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
245           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
253       Each fraction descends as follows.  The left is an increment and the
254       right is reciprocal of the increment.
255
256                   X/Y
257                 /     \
258           X/Y + 1     1/(X/Y + 1)
259
260       which means
261
262                 X/Y
263               /     \
264           (X+Y)/Y  Y/(X+Y)
265
266       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
269       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
272           floor(X/Y) = count trailing 0-bits of N
273                        plus one extra if N=2^k
274
275       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
278       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
282           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
285       Plotting the N values by X,Y gives
286
287           tree_type => "AYT"
288
289           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
303       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
308       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
311       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
317           A = Y        AYT denominator is Kepler numerator
318           B = X+Y      AYT sum num+den is the Kepler denominator
319
320           X = B-A      inverse
321           Y = A
322
323   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
328           <http://oeis.org/A071766>
329
330           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
334           <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
337       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
341       If the continued fraction of X/Y is
342
343                        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
353       then the N value is bit runs of lengths a,b,c etc.
354
355           N = 1000 1000 1000 ... 1000
356               \--/ \--/ \--/     \--/
357                a+1   b    c       z-1
358
359       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
363           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
371       The result is a bit reversal of the N values in the AYT tree.
372
373           AYT  N = binary "1abcde"      AYT <-> HCS bit reversal
374           HCS  N = binary "1edcba"
375
376       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
379       Plotting by X,Y gives
380
381           tree_type => "HCS"
382
383           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
397       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
400       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
404       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
408           count 1-bits in N+1      turn at N
409           -------------------      ---------
410                  odd                 right
411                  even                left
412
413   Bird Tree
414       "tree_type=>"Bird"" selects the Bird tree,
415
416           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
421       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
425              1             1
426           --------  and  ---- + 1
427           tree + 1       tree
428
429       which means Y/(X+Y) and (X+Y)/X taking N bits low to high.
430
431           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
439       Plotting by X,Y gives
440
441           tree_type => "Bird"
442
443           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
457       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
464       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
467           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
471       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
475       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
479   Drib Tree
480       "tree_type=>"Drib"" selects the Drib tree by Ralf Hinze.
481
482           <http://oeis.org/A162911>
483
484       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
487           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
495       The descendants of each node are
496
497                 X/Y
498               /     \
499           Y/(X+Y)  (X+Y)/X
500
501       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
504           tree_type => "Drib"
505
506           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
520       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
523       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
529   L Tree
530       "tree_type=>"L"" selects the L-tree by Peter Luschny.
531
532           <http://www.oeis.org/wiki/User:Peter_Luschny/SternsDiatomic>
533
534       It's a row-reversal of the CW tree with a shift to include zero as 0/1.
535
536           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
544       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
547           tree_type => "L"
548
549           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
563       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
566   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
571           row N=2^depth to N=2^(depth+1)-1 inclusive
572
573             sum X/Y     = (3 * 2^depth - 1) / 2
574             sum X       = 3^depth
575             sum 1/(X*Y) = 1
576
577       For example the SB tree depth=2, N=4 to N=7,
578
579           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
583       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
588            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
594       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
598   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
603                            1           1           1
604           ?(r) = 2 * (1 - ---- * (1 - ---- * (1 - ---- * (1 - ...
605                           2^q0        2^q1        2^q2
606
607                            1         1            1
608                = 2 * (1 - ---- + --------- - ------------ + ... )
609                           2^q0   2^(q0+q1)   2^(q0+q1+q2)
610
611       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
616           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
621                  2*(N-Ndepth) + 1
622           ?(r) = ----------------
623                       Ndepth
624
625       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
629           N    = 1abcdef      integer, in binary
630           ?(r) = a.bcdef1     binary fraction
631
632       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
637       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
643   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
649       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
652           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
658       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
663       The X>Y pairs in the CW tree are the right leg of each node, which is N
664       odd.  so
665
666           CW tree N=3 or 5 mod 6   gives X>Y one odd the other even
667
668           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
672       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
676           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
680       These are the Jacobsthal numbers, which in binary are 101010...101 and
681       1010...1011.
682
683       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
688       The SB tree is a bit reversal of the CW, as described above, and for
689       the Pythagorean N this gives
690
691           SB tree N=0 or 2 mod 2 and N="11...." in binary
692            gives X>Y one odd the other even
693
694       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
700       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
704           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

FUNCTIONS

711       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
712       classes.
713
714       "$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
718               "SB"      Stern-Brocot
719               "CW"      Calkin-Wilf
720               "AYT"     Yu-Ting, Andreev
721               "HCS"
722               "Bird"
723               "Drib"
724               "L"
725
726       "$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
730       "($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
734           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
740   Tree Methods
741       Each point has 2 children, so the path is a complete binary tree.
742
743       "@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
747           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
750       "$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
754       "$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
758           This is simply Nparent = floor(N/2), ie. strip the least
759           significant bit from $n.  (Undo what "tree_n_children()" appends.)
760
761       "$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
766           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
769           The L tree starts at N=0 and the calculation becomes
770           floor(log2(N+1)) there.
771
772       "$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
778           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
782   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
788       "$bool = $path->tree_any_leaf()"
789           Return false, since there are no leaf nodes in the tree.
790

OEIS

792       The trees are in Sloane's Online Encyclopedia of Integer Sequences in
793       various forms,
794
795           <http://oeis.org/A007305> (etc)
796
797           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
807           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
818           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
825           tree_type=HCS
826             A229742   X, extra initial 0/1
827             A071766   Y
828             A071585   X+Y sum
829
830           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
836           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
842           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
848           tree_type=SB,CW,AYT,HCS,Bird,Drib,L
849             A008776   total X+Y in row, being 2*3^depth
850
851           A000523  tree_n_to_depth(), being floor(log2(N))
852
853           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
862           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
868           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
875           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
880           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
884       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

SEE ALSO

890       Math::PlanePath, Math::PlanePath::FractionsTree,
891       Math::PlanePath::CfracDigits, Math::PlanePath::ChanTree
892
893       Math::PlanePath::CoprimeColumns, Math::PlanePath::DiagonalRationals,
894       Math::PlanePath::FactorRationals, Math::PlanePath::GcdRationals,
895       Math::PlanePath::PythagoreanTree
896
897       Math::NumSeq::SternDiatomic, Math::ContinuedFraction
898

HOME PAGE

900       <http://user42.tuxfamily.org/math-planepath/index.html>
901

LICENSE

903       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
904       Kevin Ryde
905
906       This file is part of Math-PlanePath.
907
908       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
913       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
918       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/>.
920
921
922
923perl v5.34.0                      2021-07-22 Math::PlanePath::RationalsTree(3)
Impressum