Math::PlanePath::CfracDigits -- continued fraction terms encoded by digits
use Math::PlanePath::CfracDigits; my $path = Math::PlanePath::CfracDigits->new (tree_type => 'Kepler'); my ($x, $y) = $path->n_to_xy (123);
This path enumerates fractions 0 < X/Y < 1 with X,Y no common factor, using a method by Jeffrey Shallit encoding continued fraction terms in digit strings.
"Number Theory and Formal Languages" part 3 https://cs.uwaterloo.ca/~shallit/Papers/ntfl.ps
Fractions up to a given denominator are covered by roughly N=den^2.28. This is a much smaller range than the run-length encoding in RationalsTree and FractionsTree (but is more than GcdRationals).
15 | 25 27 91 61 115 307 105 104 14 | 23 48 65 119 111 103 13 | 22 24 46 29 66 59 113 120 101 109 99 98 12 | 17 60 114 97 11 | 16 18 30 64 58 112 118 102 96 95 10 | 14 28 100 94 9 | 13 15 20 38 36 35 8 | 8 21 39 34 7 | 7 9 19 37 33 32 6 | 5 31 5 | 4 6 12 11 4 | 2 10 3 | 1 3 2 | 0 1 | Y=0 | ---------------------------------------------------------- X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A fraction 0<X/Y<1 has a finite continued fraction
1 X/Y = 0 + --------------------- 1 q[1] + ----------------- 1 q[2] + ------------ .... 1 q[k-1] + ---- q[k] where q[i] >= 1 and q[k] >= 2 last term
The terms are collected up as a sequence of integers >=0 by subtracting 1 from each and 2 from the last.
q[1]-1, q[2]-1, ..., q[k-2]-1, q[k-1]-1, q[k]-2
These integers are written in base-2 using digits 1,2. A digit 3 is written between each term as a separator.
base2(q[1]-1), 3, base2(q[2]-1), 3, ..., 3, base2(q[k]-2)
If q[i]-1 etc term is 0 then its base-2 form is empty and there's adjacent 3s in that case. If the high q[1]-1 is zero then a bare high 3, or similarly a final 3 if q[k]-2 is zero. If there's just a single term q[1] with q[1]-2=0 then the string is completely empty, which is so for X/Y=1/2.
The resulting string of 1s,2s,3s is reckoned as a base-3 value with digits 1,2,3 and the result is N. All possible strings of 1s,2s,3s occur and so all integers N>=0 correspond one-to-one with an X/Y fraction.
Using digits 1,2 means writing an integer in the form
d[k]*2^k + d[k-1]*2^(k-1) + ... + d[2]*2^2 + d[1]*2 + d[0] where each digit d[i]=1 or 2
and similarly base-3 with digits 1,2,3 as used for N,
d[k]*3^k + d[k-1]*3^(k-1) + ... + d[2]*3^2 + d[1]*3 + d[0] where each digit d[i]=1, 2 or 3
This is not the same as the conventional radix representation by digits 0 to R-1. The effect of 1 to R is to change a 0 digit to instead R and decrement the value above that position to compensate.
N=0,1,2,4,5,7,etc in the X=1 column is integers with no digit 0 in ternary (N=0 considered no digits at all). This is fractions 1/Y which are a single term q[1]=Y-1 and hence no "3" separators, only digits 1,2. These N values are also those which are the same in digits 0,1,2 as in digits 1,2,3, since there's no 0s or 3s.
N=0,3,10,11,31,etc along the diagonal Y=X+1 are no digit 0 in ternary except for an initial "10". Those points are Y/(Y+1) which is continued fraction
1 Y/(Y+1) = 0 + ----- 1 + 1/Y
so q0=1 and q1=Y, giving N="3,Y-1" in digits 1,2,3, which is N="1,0,Y-1" in normal ternary. For example N=34 is ternary 1021 which is leading "10" and then Y-1=7 is ternary "21".
The optional radix parameter can select another base for the continued fraction terms, and correspondingly radix+1 for N. The default above is radix=2. Any integer radix=1 upwards can be selected. For example,
radix
radix => 5 13 | 13 36 145 110 474 76 256 1554 1370 1405 246 227 12 | 11 444 1524 226 11 | 10 30 114 469 75 255 1549 1374 240 225 10 | 9 109 1369 224 9 | 8 24 74 254 234 223 8 | 7 78 258 41 7 | 5 18 73 253 228 40 6 | 4 39 5 | 3 12 42 38 4 | 2 37 3 | 1 6 2 | 0 1 | Y=0 | ------------------------------------------------------------- X=0 1 2 3 4 5 6 7 8 9 10 11 12
The X=1 column is integers with no digit 0 in base radix+1, so here radix=5 means no 0 digit in base 6.
The radix=1 case encodes continued fraction terms using only digit 1, which means runs of q many "1"s (ie. adding up to q), and "2" digits as separators. The result is similar to the run-length encoding in RationalsTree. In ordinary digit 0,1 binary the result is "10000" runs for the high q terms and a "1111" run for the lowest.
1000001000010000111111 ^ ^ ^ ^
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::CfracDigits->new ()
$path = Math::PlanePath::CfracDigits->new (radix => $radix)
Create and return a new path object.
$n = $path->n_start()
Return 0, the first N in the path.
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include
http://oeis.org/A032924 (etc) radix=2 A032924 N in X=1 column, ternary no digit 0 (but lacking N=0) radix=3 A023705 N in X=1 column, base-4 no digit 0 (but lacking N=0) radix=4 A023721 N in X=1 column, base-5 no digit 0 (but lacking N=0) radix=10 A052382 N in X=1 column, decimal no digit 0 (but lacking N=0)
Math::PlanePath, Math::PlanePath::FractionsTree, Math::PlanePath::CoprimeColumns
Math::PlanePath::RationalsTree, Math::PlanePath::GcdRationals, Math::PlanePath::DiagonalRationals
Math::ContinuedFraction
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2012 Kevin Ryde
This file is part of Math-PlanePath.
Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
Math-PlanePath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
To install Math::PlanePath, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::PlanePath
CPAN shell
perl -MCPAN -e shell install Math::PlanePath
For more information on module installation, please visit the detailed CPAN module installation guide.