1Math::PlanePath::CfracDUisgeirtsC(o3n)tributed Perl DocuMmaetnht:a:tPiloannePath::CfracDigits(3)
2
6 Math::PlanePath::CfracDigits -- continued fraction terms encoded by
7 digits
8
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
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 Jeffrey Shallit, "Number Theory and Formal Languages", part 3,
20 <https://cs.uwaterloo.ca/~shallit/Papers/ntfl.ps>
21 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 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 A fraction 0 < X/Y < 1 has a finite continued fraction of the form
46 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 where each q[i] >= 1
59 except last q[k] >= 2
60 The terms are collected up as a sequence of integers >=0 by subtracting
62 1 from each and 2 from the last.
63 # each >= 0
65 q[1]-1, q[2]-1, ..., q[k-2]-1, q[k-1]-1, q[k]-2
66 These integers are written in base-2 using digits 1,2. A digit 3 is
68 written between each term as a separator.
69 base2(q[1]-1), 3, base2(q[2]-1), 3, ..., 3, base2(q[k]-2)
71 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 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 Digits 1,2 in base-2 means writing an integer in the form
84 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 Similarly digits 1,2,3 in base-3 which is used for N,
89 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 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 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 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 1
112 X/(X+1) = 0 + -------
113 1
114 1 + ---
115 X
116 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 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 radix => 5
128 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 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 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 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 which becomes in plain binary
157 N = 100000 10000 ... 10000 011111 base2 digits 0,1
159 \----/ \---/ \---/ \----/
160 q[1] q[2] q[k-1] q[k]-1
161 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 radix => 1
168 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 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 CfracDigits radix=1 RationalsTree tree_type=HCS
191 X/Y = 5/6 (Y-X)/X = 1/5
193 is at is at
194 N = 23 = 0b10111 N = 24 = 0b11000
195 ^^^^ ^^^^
196
198 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
199 classes.
200 "$path = Math::PlanePath::CfracDigits->new ()"
202 "$path = Math::PlanePath::CfracDigits->new (radix => $radix)"
203 Create and return a new path object.
204 "$n = $path->n_start()"
206 Return 0, the first N in the path.
207
209 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
210 this path include
211 <http://oeis.org/A032924> (etc)
213 radix=1
215 A071766 X coordinate (numerator), except extra initial 1
216 radix=2 (the default)
218 A032924 N in X=1 column, ternary no digit 0 (but lacking N=0)
219 radix=3
221 A023705 N in X=1 column, base-4 no digit 0 (but lacking N=0)
222 radix=4
224 A023721 N in X=1 column, base-5 no digit 0 (but lacking N=0)
225 radix=10
227 A052382 N in X=1 column, decimal no digit 0 (but lacking N=0)
228
230 Math::PlanePath, Math::PlanePath::FractionsTree,
231 Math::PlanePath::CoprimeColumns
232 Math::PlanePath::RationalsTree, Math::PlanePath::GcdRationals,
234 Math::PlanePath::DiagonalRationals
235 Math::ContinuedFraction
237
239 <http://user42.tuxfamily.org/math-planepath/index.html>
240
242 Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin
243 Ryde
244 This file is part of Math-PlanePath.
246 Math-PlanePath is free software; you can redistribute it and/or modify
248 it under the terms of the GNU General Public License as published by
249 the Free Software Foundation; either version 3, or (at your option) any
250 later version.
251 Math-PlanePath is distributed in the hope that it will be useful, but
253 WITHOUT ANY WARRANTY; without even the implied warranty of
254 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
255 General Public License for more details.
256 You should have received a copy of the GNU General Public License along
258 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
259perl v5.34.0 2021-07-22 Math::PlanePath::CfracDigits(3)