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, 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 N range than the runlength 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[k1] + 
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[k2]1, q[k1]1, q[k]2
These integers are written in base2 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 base2 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 base3 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 onetoone with an X/Y fraction with no common factor.
Digits 1,2 in base2 means writing an integer in the form
d[k]*2^k + d[k1]*2^(k1) + ... + d[2]*2^2 + d[1]*2 + d[0]
where each digit d[i]=1 or 2
Similarly digits 1,2,3 in base3 which is used for N,
d[k]*3^k + d[k1]*3^(k1) + ... + 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 radix1). 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]=Y1 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,X1" in digits 1,2,3, which is N="1,0,X1" in normal ternary. For example N=34 is ternary "1021" which is leading "10" and then X1=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 base6.
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[k1]1 q[k]2
which becomes in plain binary
N = 100000 10000 ... 10000 011111 base2 digits 0,1
\/ \/ \/ \/
q[1] q[2] q[k1] 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 N1 here, and a flip (YX)/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 (YX)/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
http://oeis.org/A032924 (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, base4 no digit 0 (but lacking N=0)
radix=4
A023721 N in X=1 column, base5 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
HOME PAGE
http://user42.tuxfamily.org/mathplanepath/index.html
LICENSE
Copyright 2012, 2013, 2014, 2015, 2016 Kevin Ryde
This file is part of MathPlanePath.
MathPlanePath 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.
MathPlanePath 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 MathPlanePath. If not, see <http://www.gnu.org/licenses/>.