--- name: "Math::PlanePath::CfracDigits" section: "3pm" platform: "linux" package: "libmath-planepath-perl" version: "129-1" release: "Debian 13 (Trixie)" platforms: ["linux"] url: "https://new.carta.tech/Math::PlanePath::CfracDigits" --- # Math::PlanePath::CfracDigits(3pm) ## NAME Math::PlanePath::CfracDigits -- continued fraction terms encoded by digits ## SYNOPSIS ``` use Math::PlanePath::CfracDigits; my $path = Math::PlanePath::CfracDigits->new (tree_type => 'Kepler'); my ($x, $y) = $path->n_to_xy (123); ``` ## DESCRIPTION This path enumerates reduced fractions 0 \< X/Y \< 1 with X,Y no common factor using a method by Jeffrey Shallit encoding continued fraction terms in digit strings, as per Jeffrey Shallit, "Number Theory and Formal Languages", part 3, \ Fractions up to a given denominator are covered by roughly N=den^2.28. This is a much smaller N 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 of the form ``` 1 X/Y = 0 + --------------------- 1 q[1] + ----------------- 1 q[2] + ------------ .... 1 q[k-1] + ---- q[k] where each q[i] >= 1 except last q[k] >= 2 ``` The terms are collected up as a sequence of integers \>=0 by subtracting 1 from each and 2 from the last. ``` # each >= 0 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 a term q\[i\]-1 is zero 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, and if the last q\[k\]-2 is zero then a bare final 3. If there's just a single term q\[1\] and q\[1\]-2=0 then the string is completely empty. This occurs 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 (including the empty string) and so all integers N\>=0 correspond one-to-one with an X/Y fraction with no common factor. Digits 1,2 in base-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 ``` Similarly digits 1,2,3 in base-3 which is 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 binary and ternary radix representations by digits 0,1 or 0,1,2 (ie. 0 to radix-1). The effect of digits 1 to R is to change any 0 digit to instead R and decrement the value above that position to compensate. ### Axis Values N=0,1,2,4,5,7,etc in the X=1 column is integers with no digit 0s in ternary. N=0 is considered no digits at all and so no digit 0. These points are fractions 1/Y which are a single term q\[1\]=Y-1 and hence no "3" separators, only a run of digits 1,2. These N values are also those which are the same when written in digits 0,1,2 as when written 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 integers which are ternary "10www..." where the w's are digits 1 or 2, so no digit 0s except the initial "10". These points Y=X+1 points are X/(X+1) with continued fraction ``` 1 X/(X+1) = 0 + ------- 1 1 + --- X ``` so q0=1 and q1=X, giving N="3,X-1" in digits 1,2,3, which is N="1,0,X-1" in normal ternary. For example N=34 is ternary "1021" which is leading "10" and then X-1=7 ternary "21". ### Radix The optional `"radix"` parameter can select another base for the continued fraction terms, and corresponding radix+1 for the resulting N. The default is radix=2 as described above. Any integer radix\>=1 can be selected. For example, ``` radix => 5 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 ``` The X=1 column is integers with no digit 0 in base radix+1, so in radix=5 means no 0 digit in base-6. ### Radix 1 The radix=1 case encodes continued fraction terms using only digit 1, which means runs of q many "1"s to add up to q, and then digit "2" as separator. ``` N = 11111 2 1111 2 ... 2 1111 2 11111 base2 digits 1,2 \---/ \--/ \--/ \---/ q[1]-1 q[2]-1 q[k-1]-1 q[k]-2 ``` which becomes in plain binary ``` N = 100000 10000 ... 10000 011111 base2 digits 0,1 \----/ \---/ \---/ \----/ q[1] q[2] q[k-1] q[k]-1 ``` Each "2" becomes "0" in plain binary and carry +1 into the run of 1s above it. That carry propagates through those 1s, turning them into 0s, and stops at the "0" above them (which had been a "2"). The low run of 1s from q\[k\]-2 has no "2" below it and is therefore unchanged. ``` radix => 1 11 | 511 32 18 21 39 55 29 26 48 767 10 | 255 17 25 383 9 | 127 16 19 27 24 191 8 | 63 10 14 95 7 | 31 8 9 13 12 47 6 | 15 23 5 | 7 4 6 11 4 | 3 5 3 | 1 2 2 | 0 1 | Y=0 | ------------------------------------------- X=0 1 2 3 4 5 6 7 8 9 10 ``` The result is similar to "HCS Continued Fraction" in Math::PlanePath::RationalsTree. But the lowest run is "0111" here, instead of "1000" as it is in the HCS. So N-1 here, and a flip (Y-X)/X to map from X/Y\<1 here to instead all rationals for the HCS tree. For example ``` CfracDigits radix=1 RationalsTree tree_type=HCS X/Y = 5/6 (Y-X)/X = 1/5 is at is at N = 23 = 0b10111 N = 24 = 0b11000 ^^^^ ^^^^ ``` ## FUNCTIONS 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. ## OEIS Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include \ (etc) ``` radix=1 A071766 X coordinate (numerator), except extra initial 1 radix=2 (the default) 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) ``` ## SEE ALSO Math::PlanePath, Math::PlanePath::FractionsTree, Math::PlanePath::CoprimeColumns Math::PlanePath::RationalsTree, Math::PlanePath::GcdRationals, Math::PlanePath::DiagonalRationals Math::ContinuedFraction ## HOME PAGE \ ## LICENSE Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 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 \.