1Math::PlanePath::CfracDUisgeirtsC(o3n)tributed Perl DocuMmaetnht:a:tPiloannePath::CfracDigits(3)
2
3
4

NAME

6       Math::PlanePath::CfracDigits -- continued fraction terms encoded by
7       digits
8

SYNOPSIS

10        use Math::PlanePath::CfracDigits;
11        my $path = Math::PlanePath::CfracDigits->new (tree_type => 'Kepler');
12        my ($x, $y) = $path->n_to_xy (123);
13

DESCRIPTION

15       This path enumerates reduced fractions 0 < X/Y < 1 with X,Y no common
16       factor using a method by Jeffrey Shallit encoding continued fraction
17       terms in digit strings, as per
18
19           Jeffrey Shallit, "Number Theory and Formal Languages", part 3,
20           <https://cs.uwaterloo.ca/~shallit/Papers/ntfl.ps>
21
22       Fractions up to a given denominator are covered by roughly N=den^2.28.
23       This is a much smaller N range than the run-length encoding in
24       "RationalsTree" and "FractionsTree" (but is more than "GcdRationals").
25
26           15  |    25  27      91          61 115         307     105 104
27           14  |    23      48      65             119     111     103
28           13  |    22  24  46  29  66  59 113 120 101 109  99  98
29           12  |    17              60     114              97
30           11  |    16  18  30  64  58 112 118 102  96  95
31           10  |    14      28             100      94
32            9  |    13  15      20  38      36  35
33            8  |     8      21      39      34
34            7  |     7   9  19  37  33  32
35            6  |     5              31
36            5  |     4   6  12  11
37            4  |     2      10
38            3  |     1   3
39            2  |     0
40            1  |
41           Y=0 |
42                ----------------------------------------------------------
43               X=0   1   2   3   4   5   6   7   8   9  10  11  12  13  14
44
45       A fraction 0 < X/Y < 1 has a finite continued fraction of the form
46
47                             1
48           X/Y = 0 + ---------------------
49                                   1
50                     q[1] + -----------------
51                                         1
52                            q[2] + ------------
53                                ....
54                                             1
55                                   q[k-1] + ----
56                                            q[k]
57
58           where each  q[i] >= 1
59           except last q[k] >= 2
60
61       The terms are collected up as a sequence of integers >=0 by subtracting
62       1 from each and 2 from the last.
63
64           # each >= 0
65           q[1]-1,  q[2]-1, ..., q[k-2]-1, q[k-1]-1, q[k]-2
66
67       These integers are written in base-2 using digits 1,2.  A digit 3 is
68       written between each term as a separator.
69
70           base2(q[1]-1), 3, base2(q[2]-1), 3, ..., 3, base2(q[k]-2)
71
72       If a term q[i]-1 is zero then its base-2 form is empty and there's
73       adjacent 3s in that case.  If the high q[1]-1 is zero then a bare high
74       3, and if the last q[k]-2 is zero then a bare final 3.  If there's just
75       a single term q[1] and q[1]-2=0 then the string is completely empty.
76       This occurs for X/Y=1/2.
77
78       The resulting string of 1s,2s,3s is reckoned as a base-3 value with
79       digits 1,2,3 and the result is N.  All possible strings of 1s,2s,3s
80       occur (including the empty string) and so all integers N>=0 correspond
81       one-to-one with an X/Y fraction with no common factor.
82
83       Digits 1,2 in base-2 means writing an integer in the form
84
85           d[k]*2^k + d[k-1]*2^(k-1) + ... + d[2]*2^2 + d[1]*2 + d[0]
86           where each digit d[i]=1 or 2
87
88       Similarly digits 1,2,3 in base-3 which is used for N,
89
90           d[k]*3^k + d[k-1]*3^(k-1) + ... + d[2]*3^2 + d[1]*3 + d[0]
91           where each digit d[i]=1, 2 or 3
92
93       This is not the same as the conventional binary and ternary radix
94       representations by digits 0,1 or 0,1,2 (ie. 0 to radix-1).  The effect
95       of digits 1 to R is to change any 0 digit to instead R and decrement
96       the value above that position to compensate.
97
98   Axis Values
99       N=0,1,2,4,5,7,etc in the X=1 column is integers with no digit 0s in
100       ternary.  N=0 is considered no digits at all and so no digit 0.  These
101       points are fractions 1/Y which are a single term q[1]=Y-1 and hence no
102       "3" separators, only a run of digits 1,2.  These N values are also
103       those which are the same when written in digits 0,1,2 as when written
104       in digits 1,2,3, since there's no 0s or 3s.
105
106       N=0,3,10,11,31,etc along the diagonal Y=X+1 are integers which are
107       ternary "10www..." where the w's are digits 1 or 2, so no digit 0s
108       except the initial "10".  These points Y=X+1 points are X/(X+1) with
109       continued fraction
110
111                            1
112           X/(X+1) =  0 + -------
113                               1
114                          1 + ---
115                               X
116
117       so q0=1 and q1=X, giving N="3,X-1" in digits 1,2,3, which is
118       N="1,0,X-1" in normal ternary.  For example N=34 is ternary "1021"
119       which is leading "10" and then X-1=7 ternary "21".
120
121   Radix
122       The optional "radix" parameter can select another base for the
123       continued fraction terms, and corresponding radix+1 for the resulting
124       N.  The default is radix=2 as described above.  Any integer radix>=1
125       can be selected.  For example,
126
127           radix => 5
128
129           11  |    10   30  114  469   75  255 1549 1374  240  225
130           10  |     9       109                1369       224
131            9  |     8   24        74  254       234  223
132            8  |     7        78       258        41
133            7  |     5   18   73  253  228   40
134            6  |     4                  39
135            5  |     3   12   42   38
136            4  |     2        37
137            3  |     1    6
138            2  |     0
139            1  |
140           Y=0 |
141                ----------------------------------------------------
142               X=0   1    2    3    4    5    6    7    8    9   10
143
144       The X=1 column is integers with no digit 0 in base radix+1, so in
145       radix=5 means no 0 digit in base-6.
146
147   Radix 1
148       The radix=1 case encodes continued fraction terms using only digit 1,
149       which means runs of q many "1"s to add up to q, and then digit "2" as
150       separator.
151
152           N =  11111 2 1111 2 ... 2 1111 2 11111     base2 digits 1,2
153                \---/   \--/         \--/   \---/
154                q[1]-1  q[2]-1     q[k-1]-1 q[k]-2
155
156       which becomes in plain binary
157
158           N = 100000  10000   ...  10000  011111     base2 digits 0,1
159               \----/  \---/        \---/  \----/
160                q[1]    q[2]       q[k-1]  q[k]-1
161
162       Each "2" becomes "0" in plain binary and carry +1 into the run of 1s
163       above it.  That carry propagates through those 1s, turning them into
164       0s, and stops at the "0" above them (which had been a "2").  The low
165       run of 1s from q[k]-2 has no "2" below it and is therefore unchanged.
166
167           radix => 1
168
169           11  |   511  32  18  21  39  55  29  26  48 767
170           10  |   255      17              25     383
171            9  |   127  16      19  27      24 191
172            8  |    63      10      14      95
173            7  |    31   8   9  13  12  47
174            6  |    15              23
175            5  |     7   4   6  11
176            4  |     3       5
177            3  |     1   2
178            2  |     0
179            1  |
180           Y=0 |
181                -------------------------------------------
182               X=0   1   2   3   4   5   6   7   8   9  10
183
184       The result is similar to "HCS Continued Fraction" in
185       Math::PlanePath::RationalsTree.  But the lowest run is "0111" here,
186       instead of "1000" as it is in the HCS.  So N-1 here, and a flip (Y-X)/X
187       to map from X/Y<1 here to instead all rationals for the HCS tree.  For
188       example
189
190           CfracDigits radix=1       RationalsTree tree_type=HCS
191
192           X/Y = 5/6                 (Y-X)/X = 1/5
193           is at                     is at
194           N = 23 = 0b10111          N = 24 = 0b11000
195                       ^^^^                      ^^^^
196

FUNCTIONS

198       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
199       classes.
200
201       "$path = Math::PlanePath::CfracDigits->new ()"
202       "$path = Math::PlanePath::CfracDigits->new (radix => $radix)"
203           Create and return a new path object.
204
205       "$n = $path->n_start()"
206           Return 0, the first N in the path.
207

OEIS

209       Entries in Sloane's Online Encyclopedia of Integer Sequences related to
210       this path include
211
212           <http://oeis.org/A032924> (etc)
213
214           radix=1
215             A071766    X coordinate (numerator), except extra initial 1
216
217           radix=2 (the default)
218             A032924    N in X=1 column, ternary no digit 0 (but lacking N=0)
219
220           radix=3
221             A023705    N in X=1 column, base-4 no digit 0 (but lacking N=0)
222
223           radix=4
224             A023721    N in X=1 column, base-5 no digit 0 (but lacking N=0)
225
226           radix=10
227             A052382    N in X=1 column, decimal no digit 0 (but lacking N=0)
228

SEE ALSO

230       Math::PlanePath, Math::PlanePath::FractionsTree,
231       Math::PlanePath::CoprimeColumns
232
233       Math::PlanePath::RationalsTree, Math::PlanePath::GcdRationals,
234       Math::PlanePath::DiagonalRationals
235
236       Math::ContinuedFraction
237

HOME PAGE

239       <http://user42.tuxfamily.org/math-planepath/index.html>
240

LICENSE

242       Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
243
244       This file is part of Math-PlanePath.
245
246       Math-PlanePath is free software; you can redistribute it and/or modify
247       it under the terms of the GNU General Public License as published by
248       the Free Software Foundation; either version 3, or (at your option) any
249       later version.
250
251       Math-PlanePath is distributed in the hope that it will be useful, but
252       WITHOUT ANY WARRANTY; without even the implied warranty of
253       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
254       General Public License for more details.
255
256       You should have received a copy of the GNU General Public License along
257       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
258
259
260
261perl v5.30.1                      2020-01-30   Math::PlanePath::CfracDigits(3)
Impressum