.\" Automatically generated by Pod::Man 4.14 (Pod::Simple 3.40) .\" .\" Standard preamble: .\" ======================================================================== .de Sp \" Vertical space (when we can't use .PP) .if t .sp .5v .if n .sp .. .de Vb \" Begin verbatim text .ft CW .nf .ne \\$1 .. .de Ve \" End verbatim text .ft R .fi .. .\" Set up some character translations and predefined strings. \*(-- will .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left .\" double quote, and \*(R" will give a right double quote. \*(C+ will .\" give a nicer C++. Capital omega is used to do unbreakable dashes and .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff, .\" nothing in troff, for use with C<>. .tr \(*W- .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' .ie n \{\ . ds -- \(*W- . ds PI pi . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch . ds L" "" . ds R" "" . ds C` "" . ds C' "" 'br\} .el\{\ . ds -- \|\(em\| . ds PI \(*p . ds L" `` . ds R" '' . ds C` . ds C' 'br\} .\" .\" Escape single quotes in literal strings from groff's Unicode transform. .ie \n(.g .ds Aq \(aq .el .ds Aq ' .\" .\" If the F register is >0, we'll generate index entries on stderr for .\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index .\" entries marked with X<> in POD. Of course, you'll have to process the .\" output yourself in some meaningful fashion. .\" .\" Avoid warning from groff about undefined register 'F'. .de IX .. .nr rF 0 .if \n(.g .if rF .nr rF 1 .if (\n(rF:(\n(.g==0)) \{\ . if \nF \{\ . de IX . tm Index:\\$1\t\\n%\t"\\$2" .. . if !\nF==2 \{\ . nr % 0 . nr F 2 . \} . \} .\} .rr rF .\" ======================================================================== .\" .IX Title "Math::PlanePath::CfracDigits 3pm" .TH Math::PlanePath::CfracDigits 3pm "2021-01-23" "perl v5.32.0" "User Contributed Perl Documentation" .\" For nroff, turn off justification. Always turn off hyphenation; it makes .\" way too many mistakes in technical documents. .if n .ad l .nh .SH "NAME" Math::PlanePath::CfracDigits \-\- continued fraction terms encoded by digits .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::CfracDigits; \& my $path = Math::PlanePath::CfracDigits\->new (tree_type => \*(AqKepler\*(Aq); \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "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 .IX Xref "Shallit, Jeffrey" .Sp .RS 4 Jeffrey Shallit, \*(L"Number Theory and Formal Languages\*(R", part 3, .RE .PP 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 \f(CW\*(C`RationalsTree\*(C'\fR and \f(CW\*(C`FractionsTree\*(C'\fR (but is more than \f(CW\*(C`GcdRationals\*(C'\fR). .PP .Vb 10 \& 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 .Ve .PP A fraction 0 < X/Y < 1 has a finite continued fraction of the form .PP .Vb 10 \& 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 .Ve .PP The terms are collected up as a sequence of integers >=0 by subtracting 1 from each and 2 from the last. .PP .Vb 2 \& # each >= 0 \& q[1]\-1, q[2]\-1, ..., q[k\-2]\-1, q[k\-1]\-1, q[k]\-2 .Ve .PP These integers are written in base\-2 using digits 1,2. A digit 3 is written between each term as a separator. .PP .Vb 1 \& base2(q[1]\-1), 3, base2(q[2]\-1), 3, ..., 3, base2(q[k]\-2) .Ve .PP 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. .PP 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. .PP Digits 1,2 in base\-2 means writing an integer in the form .PP .Vb 2 \& 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 .Ve .PP Similarly digits 1,2,3 in base\-3 which is used for N, .PP .Vb 2 \& 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 .Ve .PP 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. .SS "Axis Values" .IX Subsection "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 \*(L"3\*(R" 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. .PP N=0,3,10,11,31,etc along the diagonal Y=X+1 are integers which are ternary \&\*(L"10www...\*(R" where the w's are digits 1 or 2, so no digit 0s except the initial \*(L"10\*(R". These points Y=X+1 points are X/(X+1) with continued fraction .PP .Vb 5 \& 1 \& X/(X+1) = 0 + \-\-\-\-\-\-\- \& 1 \& 1 + \-\-\- \& X .Ve .PP so q0=1 and q1=X, giving N=\*(L"3,X\-1\*(R" in digits 1,2,3, which is N=\*(L"1,0,X\-1\*(R" in normal ternary. For example N=34 is ternary \*(L"1021\*(R" which is leading \*(L"10\*(R" and then X\-1=7 ternary \*(L"21\*(R". .SS "Radix" .IX Subsection "Radix" The optional \f(CW\*(C`radix\*(C'\fR 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, .PP .Vb 1 \& 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 .Ve .PP 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. .SS "Radix 1" .IX Subsection "Radix 1" The radix=1 case encodes continued fraction terms using only digit 1, which means runs of q many \*(L"1\*(R"s to add up to q, and then digit \*(L"2\*(R" as separator. .PP .Vb 3 \& N = 11111 2 1111 2 ... 2 1111 2 11111 base2 digits 1,2 \& \e\-\-\-/ \e\-\-/ \e\-\-/ \e\-\-\-/ \& q[1]\-1 q[2]\-1 q[k\-1]\-1 q[k]\-2 .Ve .PP which becomes in plain binary .PP .Vb 3 \& N = 100000 10000 ... 10000 011111 base2 digits 0,1 \& \e\-\-\-\-/ \e\-\-\-/ \e\-\-\-/ \e\-\-\-\-/ \& q[1] q[2] q[k\-1] q[k]\-1 .Ve .PP Each \*(L"2\*(R" becomes \*(L"0\*(R" 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 \*(L"0\*(R" above them (which had been a \*(L"2\*(R"). The low run of 1s from q[k]\-2 has no \*(L"2\*(R" below it and is therefore unchanged. .PP .Vb 1 \& 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 .Ve .PP The result is similar to \*(L"\s-1HCS\s0 Continued Fraction\*(R" in Math::PlanePath::RationalsTree. But the lowest run is \*(L"0111\*(R" here, instead of \*(L"1000\*(R" as it is in the \s-1HCS.\s0 So N\-1 here, and a flip (Y\-X)/X to map from X/Y<1 here to instead all rationals for the \s-1HCS\s0 tree. For example .PP .Vb 1 \& 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 \& ^^^^ ^^^^ .Ve .SH "FUNCTIONS" .IX Header "FUNCTIONS" See \*(L"\s-1FUNCTIONS\*(R"\s0 in Math::PlanePath for behaviour common to all path classes. .ie n .IP """$path = Math::PlanePath::CfracDigits\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::CfracDigits\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::CfracDigits->new ()" .PD 0 .ie n .IP """$path = Math::PlanePath::CfracDigits\->new (radix => $radix)""" 4 .el .IP "\f(CW$path = Math::PlanePath::CfracDigits\->new (radix => $radix)\fR" 4 .IX Item "$path = Math::PlanePath::CfracDigits->new (radix => $radix)" .PD Create and return a new path object. .ie n .IP """$n = $path\->n_start()""" 4 .el .IP "\f(CW$n = $path\->n_start()\fR" 4 .IX Item "$n = $path->n_start()" Return 0, the first N in the path. .SH "OEIS" .IX Header "OEIS" Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include .Sp .RS 4 (etc) .RE .PP .Vb 2 \& 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) .Ve .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::FractionsTree, Math::PlanePath::CoprimeColumns .PP Math::PlanePath::RationalsTree, Math::PlanePath::GcdRationals, Math::PlanePath::DiagonalRationals .PP Math::ContinuedFraction .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde .PP This file is part of Math-PlanePath. .PP Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the \s-1GNU\s0 General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. .PP Math-PlanePath is distributed in the hope that it will be useful, but \&\s-1WITHOUT ANY WARRANTY\s0; without even the implied warranty of \s-1MERCHANTABILITY\s0 or \s-1FITNESS FOR A PARTICULAR PURPOSE.\s0 See the \s-1GNU\s0 General Public License for more details. .PP You should have received a copy of the \s-1GNU\s0 General Public License along with Math-PlanePath. If not, see .